leetCode33. 搜索旋转排序数组

leetCode33. 搜索旋转排序数组

---

题目思路

此题的特点是：排好序循环的数组：特点：可以分为两个区间，一半升序，一半降序，或者全部升序
我们可以用二分法，找出升序 到降序的那个临界值，并记录号那个临界值
然后在用target 跟nums[0]进行比较（因为他是升序的首元素，升序部分它最小），从而判断往左区间走还是往右区间走
更新新的区间后
在用二分法找到这个target
力扣特色：必须判断数组为空的情况

---

代码

class Solution {
public:int search(vector<int>& nums, int target) {if(nums.empty()) return -1;int left = 0, right = nums.size() - 1;// 第一个二分：找出区间临界点(升区间的临界点) 区间是找出升序的区间while(left < right){ // 模板一int mid = left + right + 1 >> 1;if(nums[mid] >= nums[0]) left = mid;else right = mid - 1;} // left == right// 找target是往左右那个升区间走if(target >= nums[0]) left = 0;else {left = right + 1;right = nums.size() - 1;}// 第二次二分找出那个target的下标while(left < right){ // 模板二int mid = left + (right - left >> 1);if(nums[mid] >= target) right = mid;else left = mid + 1;} // left >= rightif(nums[right] == target) return right; // 返回的一定使用right进行比较的，因为left的值会大于right,用left的话说不定会越界else return -1;}
};