# 查找
# 1. 二分查找
二分查找，最终收敛为一个值。
该值为目标值，或最接近目标值的一个，不能确定其是大于目标值还是小于目标值。
# 1.1 一般写法
如查找一个排序数组中的某个元素：
const biSearch = (nums, target) => {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 1.2 变体
如力扣第 33 题 搜索旋转排序数组 (opens new window)。
在一个部分有序的数组中寻找目标值，同样也是使用二分查找，但是需要进行一定的变体。
var search = function(nums, target) {
const len = nums.length;
let left = 0, right = len - 1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] >= nums[0]) { // 左半区有序
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右半区有序
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27