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