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

下面继续提高难度，如果上面的那道题数组是可重复的呢？

例题：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所在的位置。

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