题目描述
搜索旋转排序数组
思路
思路来源
一个清晰的思路:这道题和平常二分法查找的不同就在于,把一个有序递增的数组分成了,两个递增的数组,我们需要做的就是判断这个数在哪一个递增的数组中,然后再去用常规的二分法去解决
代码1
class Solution {
public:int search(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n - 1;while(l < r){int mid = l + r >> 1;if(nums[0] <= nums[mid] && nums[0] <= target && target <= nums[mid]){r = mid;}else if(nums[mid] < nums[0] && target <= nums[mid]){r = mid;}else if(nums[mid] < nums[0] && nums[0] <= target){r = mid;}else {l = mid + 1;}}return nums[l] == target ? l : -1;}
};
位运算优化版
class Solution {
public:int search(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n - 1;while(l < r){int mid = l + r >> 1;if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])){l = mid + 1;}else {r = mid;}}return nums[l] == target ? l : -1;}
};