公众号merlinsea
题目描述
整数数组 nums 按升序排列，数组中的值 互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转。使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
示例
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
解题思路
采用二分查找，不断的压缩一半的元素，直到最后找到或者无条件可以找为止。但本题中数组旋转了，那么怎么样才能判断应该向左压缩还是应该向右压缩呢？核心点：
1、如何判断数组[left,right]区间是否发生了反转
2、在[left,right]区间有反转的情况下如何判断mid是落在左半部分还是右半部分
3、前两步完成的情况下，如何判断应该移动左指针还是移动右指针。
代码
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length-1; while(left<=right){ int mid = (left+right)/2; if(nums[left] < nums[right]){ //说明整个数组从[left,right]区间升序 if(target==nums[mid]){ return mid; }else if(target>nums[mid]){ left = mid+1; }else{ right = mid-1; } }else{ //说明整个数组从[left,right]区间是中间旋转了 if(nums[mid]>=nums[left]){ //说明前半段[left,mid]是严格升序的，即mid落在前半段 if(target==nums[mid]){ return mid; }else if(target>nums[mid] || target<nums[left]){ //4 5 6 7 8 1 2 3 left = mid+1; }else{ right = mid-1; } }else{ //说明后半段[mid,right]是严格升序的，即mid落在后半段 if(target==nums[mid]){ return mid; }else if(target<nums[mid] || target>nums[right]){ //6 7 8 1 2 3 4 5 right = mid-1; }else{ left = mid+1; } } } } return -1; } }
