二分查找详解
写法一：
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
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = (int)nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
int searchInsert(vector<int>& nums, int target) {
// 返回第一个值大于等于target的下标
int left = 0, right = (int)nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left; // left右侧的位置都大于等于left，left左侧位置都小于left
}
如果数组为[1,3,5,6]，target=2；
left = 0, right = 3（均为位置）
第一轮 mid=1, left=0, right=0;
第二轮 mid=0, left=1,right=1;
总结：当target不在数组时，需要返回按顺序插入的位置，也就是第一个比target大的位置。因此返回left是最佳方案，right只会是比target小的第一个位置。
写法二：
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
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
28
29
30
31
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() == 0)
return vector<int>{-1, -1};
int l1 = -1, l2 = -1;
int left = 0, right = (int)nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] >= target) { // 找出第一个大于等于target的下标
right = mid - 1;
} else {
left = mid + 1;
}
}
if (left < nums.size() && nums[left] == target)
l1 = left;
left = 0, right = (int)nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] <= target) { // 找出第一个小于等于target的下标
left = mid + 1;
} else {
right = mid - 1;
}
}
if (right < nums.size() && nums[right] == target)
l2 = right;
return vector<int>{l1, l2};
}
进阶：寻找峰值
1
2
3
4
5
6
7
8
9
10
11
12
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] > nums[mid + 1]) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
