【LeetCode-中等】33.搜索旋转排序数组 - 二分法

力扣题目链接

思路：

• 数组按升序排序，时间复杂度要求O(log n) -> 二分法
• 数组经过未知旋转 -> 数组部分有序 -> mid一定会将数组分为有序和无序的两部分 -> 通过比较 nums[left] 和 nums[mid] 的大小判断哪部分数组是有序的 -> 判断 target 是否在有序区间内 -> 判断移动 left 还是 right

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int left = 0, right = len - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }
            //nums[left]~nums[mid]有序
            if(nums[left] <= nums[mid]){
                if(nums[left] <= target && target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            //nums[mid]~nums[right]有序
            else{
                if(nums[mid] < target && target <= nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30