这几天刷LeetCode中二分查找相关的题目,思想总是没什么问题,总是被各种边界条件折磨地死去活来,提交1次错一次,完全是面向测试编程,好不容易把下标调整对了,可是当下次遇到这个题目的时候还是需要从头再错一边😿。我们先来看一下最朴素的二分查找,看看存在怎样的问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binarySearch(arr, target) {
let l = 0, r = arr.length - 1;
while (l <= r) {
const mid = (l + r) >> 1;
const num = arr[mid];
if (target === num) {
return mid;
}
if (target < num) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}
  1. 为啥是l = mid + 1,r = mid - 1,而不是l = mid,r = mid。