leetcode 33. 搜索旋转排序数组

2023.9.26

        本题暴力法可以直接A，但是题目要求用log n的解法。 可以想到二分法，但是一般二分法适用于有序数组的，这里的数组只是部分有序，还能用二分法吗？ 答案是可以的。因为数组是经过有序数组旋转得来的，所以在二分之后，左右两边必有一边是有序的。  具体细节看代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            //左半边升序的情况
            if(nums[0] <= nums[mid])
            {
                if(target < nums[mid] && target >= nums[0])
                {
                    right = mid - 1;
                }
                else left = mid + 1;
            }
            //右半边升序的情况
            else
            {
                if(target > nums[mid] && target <= nums[nums.size()-1])
                {
                    left = mid + 1;
                }
                else right = mid - 1;
            }
        }
        return -1;
    }
};