时间复杂度
logN
二分查找的实现可以分为两种，一种是递归式的、另一种是循环式的
😜递归式
1
2
3
4
5
6
7
8
9
10
11
12
| int BinarySearch(vector<int>& a,int lo,int ho, int key) {
// if(lo > ho) return -1;
// int mid = (lo + ho) / 2;
// if(a[mid] > key) return BinarySearch(a, lo, mid - 1, key);
// else if(a[mid] < key) BinarySearch(a, mid + 1, ho, key);
// else return mid;
if(lo >= ho) return -1;
int mid = (lo + ho) / 2;
if(a[mid] > key) return BinarySearch(a, lo, mid, key);
else if(a[mid] < key) BinarySearch(a, mid + 1, ho, key);
else return mid;
}
|
区间的开闭自由选取，主要是要统一，如果要求传入左闭右开区间，那么在函数内部的处理也要保持左闭右开。
一般的选择应该时左右都是闭区间，而在特殊情况时（数组中有多个相同的目标时），这时选择左闭右开。
🥛参考：wiki链接
为了避免ho + lo 大于INT_MAX最好改用lo + (ho - lo) / 2
🈶非递归式
1
2
3
4
5
6
7
8
9
10
11
12
| int BinarySearch(vector<int>& a, int key) {
int lo = 0,
ho = a.size(),
mid;
while(lo < ho) {
mid = (lo + ho) / 2;
if(a[mid] > key) ho = mid;
else if(a[mid] < key) lo = mid + 1;
else return mid;
}
return -1;
}
|
递归要满足三个原则：
- 递归总有一个最简单的情况—方法的第一句总是一个包含return的条件语句。
- 递归调用总要尝试取解决一个规模更小的子问题。
- 递归调用的父问题和子问题之间不应该有交集。
🥘推荐相关资料：讲解
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
| class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//首先要判定拿个序列更加长
if(nums1.size() > nums2.size())
swap(nums1, nums2);
//左闭右开
int imin = 0,
imax = nums1.size(),
j, i,
m = nums1.size(),
n = nums2.size(),
halflen = (m + n + 1) / 2;
while(imin <= imax) {
i = (imax + imin ) / 2;
j = halflen - i;
// cout << i << j << endl;
if (j <= n && i < imax && nums1[i] < nums2[j - 1]) {
imin = i + 1;
} else if (i > imin && j < n && nums2[j] < nums1[i - 1]) {
imax = i;
} else {
// cout << "end" << endl;
int leftMax, rightMin;
if(i == 0 ) leftMax = nums2[j - 1];
else if(j == 0) leftMax = nums1[i - 1];
else leftMax = max(nums1[i - 1], nums2[j - 1]);
if((m + n) % 2) return leftMax;
if(i == m) rightMin = nums2[j ];
else if (j == n) rightMin = nums1[ i ];
else rightMin = min(nums1[i], nums2[j]) ;
// cout << leftMax << rightMin << endl;
return static_cast<double>(leftMax + rightMin) / 2;
}
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int lo = 0,
ho = nums.size() - 1,
mid;
while(lo < ho) {
mid = (lo + ho + 1) / 2;
if(nums[mid] > target) {
ho = mid - 1;
} else {
lo = mid;
}
}
if(nums[lo] < target) return lo + 1;
else return lo;
}
};
|
