力扣-33.搜索旋转排序数组

题目要求是O（logn）的时间复杂度，那么普通的遍历做法是行不通了。题中旋转排序数组（数组中无重复元素）的有一个特点：部分有序性，以中点划分，左右半段至少有一部分是有序的。那部分有序性的数组能不能用二分搜索呢，答案是可以的。

具体做法如下：

如果[l, mid]是有序的，并且target的范围在[l, mid]中，那么将搜索范围移动到[l, mid]，否则为[mid + 1, r]；
如果[mid + 1, r]是有序的，并且target的范围在[mid + 1, r]中，那么将搜索范围移动到[mid + 1, r]，否则为[l, mid]；

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return -1;  
        if (n == 1) return nums[0] == target? 0:-1;
        int l = 0, r = n - 1;
        while(l<=r){
            int mid = l + (r-l)/2;
            if (nums[mid] == target) return mid;
            if(nums[l] <= nums[mid]){
                if(nums[l]<= target && target < nums[mid]){
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            else{
                if (nums[mid] < target && target <= nums[n-1]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }  
            }
        }
        return -1; //未找到
    }    
};

代码

力扣-704，简单的二分搜索题（无重复，有序数组）

传送门

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l<=r){
            int mid = l + (r - l)/2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        return -1;
    }
};

代码

力扣-33.搜索旋转排序数组

推荐阅读