搜索旋转排序数组
- 难度： 中等
- 通过率： 32.5%
- 题目链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
解法
有序数组旋转后，可以看做两个有序数组拼接起来了。如果能够把范围限定在其中一个数组内，就可以运行二分查找。
因为旋转后的前半部分中的值一定大于后半部分，且 nums[0] 是前半部分中最小的值。
因此 nums[i] >= nums[0] 说明 i 在前半部分。否则一定在右半部分。在二分查找时，根据 nums[mid] 和 target 的位置，来调整上下界。
当 target 和 nums[mid] 在同一侧时：
- 此时和常规的二分查找相同。
当 target 和nums[mid] 不在同一侧时：
- target 在左，
nums[mid]在右，需要调小 hi，即 hi = mid - target 在右，
nums[mid]在左，需要调大 lo，即 lo = mid + 1
class Solution {
public:
int search(vector<int>& nums, int target) {
int lo = 0, hi = nums.size();
while(lo < hi){
int mid = lo + (hi - lo) / 2;
// 同一侧
if((nums[mid] < nums[0]) == (target < nums[0])){
if(nums[mid] > target){
hi = mid;
}else if(nums[mid] < target){
lo = mid + 1;
}else{
return mid;
}
}else{
if(nums[mid] > target){
lo = mid +1;
}else{
hi = mid;
}
}
}
return -1;
}
};