前言
日常刷LeetCode的时候，用暴力解决了一道困难级别的题目，其时间限制是log(m+n)，才发现真正做法是用二分查找，因此补补相关知识。
题目中有序、时间复杂度要求logn、最大值最小等，可以考虑二分查找。
一、 基本思想
二分查找也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
二、 复杂度分析
最坏情况下关键字比较次数为log(n+1),最好情况为log(n).
三、 常用的库函数 & 模板
1
2
3
|
lower_bound(sums.begin(), sums.end(), target) - sums.begin();
upper_bound(sums.begin(), sums.end(), target) - sums.begin();
|
1
2
|
sort.SearchInts(sums, target)
|
有序数组中的二分查找分为以下四种类型，这四种类型可以互相转换的（对于整数来说），因此以下四种类型都可以用lowerBound模板解决：
>= target> target 可以转化为 >= target + 1< target 可以转化为 <= target-1<= target可以转化为 > target - 1
查找nums中第一个>=target的数的数，lowerBound模板：
1
2
3
4
5
6
7
8
9
10
11
12
| func lowerBound(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return left
}
|
四、 例题
LeetCode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int search(vector<int>& nums, int target) {
int n = nums.size();
int start = 0;
int end = n-1;
int mid;
while(start <= end)
{
mid = (start+end)/2;
if(target == nums[mid])
return mid;
else if(nums[mid] > target)
{
end = mid-1;
}
else
{
start = mid+1;
}
}
return -1;
}
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| int left(vector<int> nums,int target)
{
int left = 0;
int right = nums.size() - 1;
int mid;
while(left <= right)
{
mid = (left + right) / 2;
if(nums[mid] > target)
{
right = mid - 1;
}
else if(nums[mid] < target)
{
left = mid + 1;
}
else if(mid-1 >=0 && nums[mid-1] == target)
{
right = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
int right(vector<int> nums, int target)
{
int left = 0;
int right = nums.size() - 1;
int mid;
while(left <= right)
{
mid = (left + right) / 2;
if(nums[mid] < target)
{
left = mid + 1;
}
else if(nums[mid] > target)
{
right = mid - 1;
}
else if(mid + 1 < nums.size() && nums[mid+1] == target)
{
left = mid + 1;
}
else
return mid;
}
return -1;
}
int search(vector<int>& nums, int target) {
if(nums.size() == 0)
return 0;
int leftIdx = left(nums,target);
int rightIdx = right(nums,target);
if(leftIdx != -1 && rightIdx != -1)
return rightIdx - leftIdx + 1;
else
return 0;
}
|
旋转数组中最小的数字
通过旋转数组找出一下四个条件：（i表示左边，j表示右边，m表示中间）
①mid > right || j == i == m i = i + 1;
②mid <= right j = m; //由分治法 和右边比较
③ j - i == 1 判断左右两个元素哪个小，就赋值给m。 // 1,0,1,1,1
④ i == j m 赋值给i或者j都行。 // 2,2,2,0,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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| int minArray(vector<int>& nums) {
if(nums.size() == 0)
return 0;
int len = nums.size();
int index1 = 0;
int index2 = len - 1;
int mid = index1;
int min = 0;
while(nums[index1] >= nums[index2])
{
mid = (index1 + index2) / 2;
if(index2 == index1)
{
mid = index1;
break;
}
else if(nums[mid] >= nums[index2] || (nums[index1] == nums[mid] && nums[index1] == nums[index2]))
{
index1 += 1;
if(nums[index1] < nums[index2])
{
mid = index1;
break;
}
}
else if(nums[mid] <= nums[index2])
{
index2 = mid;
}
else if(index2 - index1 == 1)
{
if(nums[index2] > nums[index1])
{
mid = index1;
break;
}
else
{
mid = index2;
break;
}
}
}
return nums[mid];
}
|
