题解 | #<图示详解>在旋转过的有序数组中寻找目标值#

思路：二分法

• 我们知道二分法适用于有序数组，并且题中告诉我们数组严格升序，只是经过了旋转，经过一番思考，我们可以充分利用好以上性质，写出让 面试官 想要的代码。
• 旋转后的数组分为两部分，[low...mid]和[mid...high]，这两部分必有一个是有序数组，我们考虑每次都处理有序的那部分，进行范围的精确定位，具体做法看下面的图解。

复杂度

时间复杂度O(log n)，空间复杂度O(1)

图示

图1：

图2：

图3：

图4：

代码（Java）

public class Solution {
	int search (int[] nums, int target) {//二分法
		if(nums==null||nums.length==0||target<0) return -1;
		int low=0,high=nums.length-1;
		int mid=0;
		while(low<=high) {
			mid=low+(high-low)/2;
			if(nums[mid]==target) return mid;//先将target和nums[mid]比较
			else if(nums[low]<nums[mid]) {//有序区间在low...mid
				if(target>nums[mid]||target<nums[low]) {//不在区间内，对应于图中情形1
					low=mid+1;
				}
				else high=mid-1;//在区间内，对应于图中情形2
			}
			else {//nums[mid]<nums[high],有序区间在mid...high
				if(target<nums[mid]||target>nums[high]) {//不在区间内，对应于图中情形3
					high=mid-1;
				}
				else low=mid+1;//在区间内，对应于图中情形4
			}
		}
		return -1;//不存在
	}
}