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

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;
    }
};

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