一维数组
首先开始最基本的Binary Search, 数组是有序的，但是有重复数。
例题： Search for a Range
复杂度：时间O(log n), 空间O(1).
分析： 首先需要复杂度在O(log n)左右，显然暗示了Binary Search是首选，然后注意这道题是需要找到一个range，并不是找到target的位置就可以了。因此在找到位置后，分别向左向右拓展到两边，返回这两个数就可以了。
class Solution{
public:
vector<int> searchRange(int A[], int n, int target) {
vector<int> result(2,-1);
int index = search(A, n, target);
if(index == -1) return result;
int l = index, r = index;
while(l -1 >= 0 && A[l] == A[l-1]) --l;
while(r +1 <= n-1 && A[r] == A[r+1]) ++r;
result[0] = l;
result[1] = r;
return result;
}
int search(int A[], int n , int target){
if(A == nullptr || n == 0) return -1;
int left = 0, right = n -1;
while(left <= right){
int mid = left + (right - left) /2;
if(target > A[mid])
left = mid + 1;
else if(target < A[mid])
right = mid - 1;
else if(target == A[mid])
return mid;
}
return -1;
}
};
注意这里做binary search时候，对于A[mid]分为了三种不同情况讨论，相等，小于和大于，并且while循环的终止条件是left <= right，也就是说最后left > right时候表明目标数肯定不存在了。在对于不同的问题，这些边界条件会相应的改变。另外这样搜索如果最后目标数存在，最后结果一定是以A[mid]的形式。
例题： Search Insert Position
复杂度：时间O(log n), 空间O(1).
分析：这道题的关键是如果目标数不存在，必须返回目标数可以插入的位置，这样经典的binary search返回A[mid]的方法（如上题）没法直接实现因此必须对循环的条件以及边界进行调整。首先当循环结束时候，为了能返回一个目标数可以插入的地址，我们必须让left == right也就是说循环条件相应调整为left < right. 如果需要设置循环里面的边界条件和left, right的初始条件，我们必须看一下最后一次循环时候的情况：最后一次循环时， left + 1 = right只剩下两个元素需要考虑（这里忽略数组只有一个元素的情形，因为一个元素时，程序根本不会进入循环），此时mid = left，如果target > A[mid], left = mid + 1 = right与之前情况类似，那么当target < A[mid]时候也就是说target并不存在，此时应该输出target元素需要插入的位置也就是left, 因此right = mid = left，当target = A[mid]情形与小于相同，right = mid = left.还有一种情况，当target大于数组里面所有数的时候，插入位置应该在所有数组之后，因此right的初始值必须是n，因为很容易发现前面的边界条件设置导致最后输出的left都会在两个初始值left和right之间。
class Solution {
public:
int searchInsert(int A[], int n, int target) {
if(A == nullptr || n == 0) return -1;
int left = 0, right = n ;
while(left < right){
int mid = left + (right - left) /2 ;
if(target > A[mid])
left = mid + 1;
else
right = mid;
}
return left;
}
};
接下来，问题难度提高了，数组仍然有序并且无重复数，但是在某一点pivot截断并且移动了几位。
例题： Search in Rotated Sorted Array
复杂度： 时间O(log n), 空间O(1).
分析：因为事先不知道数组会再哪里截断因此在while循环的边界条件需要调整来满足需求。因为存在数组中并不包含目标数的情况，因此希望所有循环结束时候仍然找不到目标数此时返回-1，另一方面也就是说在循环内部如果发现目标数A[mid] == target返回，当first == last时候循环结束， 判断条件与上一道题一样。下面看A[mid] != target的情形，因为pivot的存在，必须找到pivot在左边还是右边，办法就是比较A[first]和A[mid]，如果A[first] < A[mid]说明pivot不在左边这段，因为pivot会破坏所在一段的连续递增性（递减性）, 因此这里在左边用一般的binary search可以解决。如果A[first] > A[mid],pivot肯定会在左边，那么我们可以对右边进行binary search因为右边是连续递增（递减）的。下面再考虑边界条件还有初始条件，注意这里我们还是把初始条件设置为n即最后一位之后一位，那么在边界条件上需要变化，如果target属于[A[first], A[mid])之间，last变为mid，注意这里保持last是搜索范围最后一个数字的下一位。 同理在A[first] > A[mid]的情况下我们比较的是target <= A[last -1 ]由于last的初始值设置。 注意在讨论target和左右两个边界条件时候使用大于等于或者小于等于，注意等号是必须的。
class Solution {
public:
int search(int A[], int n, int target) {
if(A == nullptr || n == 0) return -1;
int first = 0, last = n;
while (first < last) {
int mid = first + (last - first) / 2;
if (A[mid] == target)
return mid;
if (A[first] < A[mid]) {
if (A[first] <= target && target < A[mid])
last = mid;
else
first = mid + 1;
} else {
if (A[mid] < target && target <= A[last-1])
first = mid + 1;
else
last = mid;
}
}
return -1;
}
};
下面继续提高难度，如果上面的那道题数组是可重复的呢？
例题：Rotated Sorted Array II
复杂度：时间O(n),空间O(1).
分析：如果出现重复数最大的问题就是当A[left] == A[mid],此时没有办法判断pivot到底在哪里，比较简单的快速解决方案就是把left右移一位继续寻找。
class Solution {
public:
bool search(int A[], int n, int target) {
if(A == nullptr|| n == 0) return false;
int left = 0, right = n;
while(left < right){
int mid = left + (right - left)/2;
if(A[mid] == target)
return true;
if(A[left] < A[mid]){
if(target < A[mid] && target >= A[left]){
right = mid;
}else{
left = mid + 1;
}
}else if(A[left] > A[mid]){
if(target <= A[right -1 ] && target > A[mid]){
left = mid + 1;
}else{
right = mid;
}
}else{
left++;
}
}
return false;
}
};
下面我们看一看数组查找的变形
例题：Find Minimum in Rotated Sorted Array
复杂度： 时间O(log n)，空间O(1).
分析：首先这道题和上两道题非常相似，唯一的区别就是目标不同：寻找最小值即pivot。首先假设变形前数组是从左至右递增，变形之后我们可以很容易发现最左边的元素num[left]永远大于最右边的元素mum[right]即num[left] > num[right]因为数组里没有重复元素。与之前不同，我们这里要找到pivot所在的区域而不是要避开，因此在循环内我们要比较的事num[mid]和num[right]之间的关系这道题不能比较num[start]和num[mid]因为没法排除特例当start == mid，如果num[mid] > num[right]即数组的递增性在右边是被破坏的，因此pivot肯定是在右边［mid+1, right]，反之则是［left, mid].最后我们考虑终结条件，我们知道pivot有一个性质就是唯一存在i so that num[i -1] > num[i],这里num[i]就是pivot.我们看一下最后一次循环的情形，此时left + 1 = right 并且mid = left， 这里如果如果num[mid] > num[right],那么pivot就是left = right = mid + 1, 反之right = left = mid，因此跳出循环后left = right就是pivot所在的位置。
class Solution {
public:
int findMin(vector<int> &num) {
if(num.empty()) return 0;
int left = 0;
int right = n - 1;
while(left < right ){
int mid = left + (right - left)/2;
if(num[mid] > num[right]){
left = mid + 1;
}else {
right = mid ;
}
}
return num[left];
}
};
继续增加难度，如果允许重复数的存在呢？
例题：Find Minimum in Rotated Sorted Array II
复杂度： 时间O(n), 空间O(1).
分析：如果出现重复数，唯一一种情况没办法处理就是A[mid] == A[left] == A[right],这次我们不采用上次的简单fix（把左边边界往右边移一位），而是写成recursive的形式在左右两边分别寻找最小值，这样复杂度会提高到O(n)了。
class Solution {
public:
int findMin(vector<int> &num) {
return findmin(num, 0, num.size() -1);
}
int findmin(vector<int> &num, int left, int right){
if(num.size() == 0) return -1;
while(left < right){
int mid = left + (right - left)/2;
if(num[mid] > num[right]){
left = mid + 1;
}else if(num[mid] < num[right]){
right = mid;
}else{
return min(findmin(num, left, mid), findmin(num, mid+1, right));
}
}
return num[left];
}
};
在我们结束探讨一维数组之前，再看一个经典的利用二分法查找的一维数组问题
例题： Median of Two Sorted Array
分析： 首先得弄明白median的定义，如果数组包含偶数个元素，median取中间两个数的平均值；如果数组包含个奇数个元素，那么median就是中间的那个数。下面继续看这道题，需要寻找的是两个排序的数组median，自然想到使用二分法来解。利用recursive的方法，每次比较数组A的中位数A[n/2]和数组B的中位数B[m/2]，比较同时在考虑比较另外两个值m/2 + n/2 + 1和k(其中k是两个数组合并后的第k个元素),这样可以确定删除哪一部分继续搜索，原则是丢弃最大中位数的右区间或者最小中位数的左区间。最后就是边界条件的确定，假设其中一个数组为空了，那么返回的就是另一个数组的最后一个数。或者如果k = 1， 那么返回两个数组中第一个元素的较小值。
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if((m+n) %2 == 1){
return findMedian(A, m, B, n, (m+n)/ 2 + 1);
}else{
return (findMedian(A, m, B, n, (m+n)/2) + findMedian(A, m, B, n, (m+n)/2 + 1))/2.0;
}
}
private:
double findMedian(int A[], int m, int B[], int n, int k){
assert(A&&B);
if(m <= 0) return B[k-1];
if(n <= 0) return A[k-1];
if(k == 1) return min(A[0], B[0]);
if(B[n/2] >= A[m/2]){
if((m/2 + n/2 + 1) >= k)
return findMedian(A, m, B, n/2, k);
else
return findMedian(A + m/2 + 1, m - (m/2 + 1), B, n, k - m/2 -1);
}else{
if((m/2 + n/2 + 1) >= k)
return findMedian(A, m/2, B, n, k);
else
return findMedian(A, m, B + n/2 + 1, n - (n/2 + 1), k - n/2 - 1);
}
}
};
这道题还有更简洁的方法，即确保A数组的个数永远不大于B数组的个数，如果不是就交换这两个数组。
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m + n;
if( total & 0x1 ){
return findMedian(A, m, B, n, total/2 + 1);
}else{
return (findMedian(A, m, B, n, total/2) + findMedian(A, m, B, n, total/2 + 1))/2.0;
}
}
private:
int findMedian(int A[], int m, int B[], int n, int k){
if(m > n) return findMedian(B, n, A, m, k);
if(m == 0) return B[k-1];
if(k == 1) return min(A[0], B[0]);
int ia = min(k/2, m), ib = k - ia;
if(A[ia-1] < B[ib-1])
return findMedian(A + ia, m -ia, B, n, k -ia);
else if(A[ia - 1] > B[ib - 1])
return findMedian(A, m, B +ib, n -ib, k -ib);
else
return A[ia - 1];
}
};
二维数组
例题： Search a 2D matrix
复杂度： 时间O(log (m*n)), 空间O(1).
分析：首先这道题中二维数组有两个特点：
- 每一行数是递增的
- 每一行第一个数都小于上一行的最后一个数
因此很自然的想到把二维数组压平为一位数组，然后使用binary search解决。
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
if(matrix.empty() || matrix.front().size()) return false;
int m = matrix.size();
int n = matrix.front().size();
int left = 0;
int right = m*n;
while(left < right){
int mid = left + (right - left) /2;
int middle = matrix[mid / n][mid % n];
if(target == middle){
return true;
}else if(target > middle){
left = mid + 1;
}else{
right = mid;
}
}
return false;
}
};
网友评论