【数据结构算法】二分查找

以前学过二分查找，但是一直忘记，过一段时间就忘记了，但是就是记着简单，但是还是忘记了，所以这次专门开篇文章记录，经典的二分查找 忘记了就过来大致瞟一眼。

一、最经典的二分查找模板（强烈建议记忆）

int binarySearch(int arr[], int n, int target) { int left = 0; int right = n - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }

二、记忆口诀

记住五步口诀：

1 定左右 2 求中间 3 看中间 4 改区间 5 找不到返回 -1

展开就是：

left = 0 right = n - 1 while(left <= right) { mid if(相等) return 小了 → 左边移动 大了 → 右边移动 }

三、用一句话理解二分查找

二分查找的核心就是：

每次把搜索范围砍一半

举例具体的实现：

例如数组

1 3 5 7 9 11 13

找9

第一次

mid = 7

因为

9 > 7

所以：

left = mid + 1

范围变成

9 11 13

继续找。

四、最容易写错的两个地方

1 mid 计算

推荐写：

int mid = left + (right - left) / 2;

防止整数溢出。

但普通写：

(left + right) / 2

也行。

2 while 条件

必须是：

left <= right

很多人写成：

left < right

会错。

五、脑子里的二分查找图

left right ↓ ↓ [1 3 5 7 9 11 13] ↑ mid

比较：

给定的target 值 和 arr[mid]

然后缩小范围。

六、一个10秒写出来的模板

主要记住这一行：

while(l <= r)

然后写：

arr[mid] 和 target 相等 return 小了 l = mid + 1 大了 r = mid - 1

就完事。