二分法查找c语言_二分法查找_二分法查找算法(4)

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， 那么返回两个数组中第一个元素的较小值。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26574-4.html