题目大意：
搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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 如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=33
解题思路分析：
本题要求使用logn的时间复杂度来解题，也就是说必须使用二分查找的思路。如果数组没有被旋转，本题则是二分查找的典型模板题目。考虑到数组被旋转过，本题就变得稍微复杂了一点，但思路并不难。我们先找到数组被旋转后的规律，举个例子，数组[1,2,3,4,5,6,7]被旋转为：
[6,7,1,2,3,4,5]
其中红色的数字是被旋转后未按照升序排序的部分，即使这样我们仍然可以使用二分法，取得数组的中间位置上的数字2，考虑一下，如果数组没被旋转，处于中间位置上的数字2，一定会大于等于区间最左边的数，并且一定小于等于区间最右边的数。但数组被旋转之后，上述两个已知条件只剩下一个能被满足，能被满足的那半个区间一定是按照升序顺序排序的区间，例如上面的例子中，满足条件的合法区间是[mid, right](2,3,4,5)。
此时我们判断target的值是否在合法区间内( target >=nums[mid] && target <=nums[right] )，如果在该区间内，我们在该区间二分查找即可。如果不在，说明target在另外半个非法排序区间内，此时，将left和right值更新为另外半个区间的坐标。继续二分该区间，查看哪半个区间是排序好的合理区间，并查看target是否在该合理区间内，在的话，开始常规二分查找，否则继续循环上述步骤即可。
实现代码：
public int search(int[] nums, int target) {
// 左指针为0，右指针为数组长度减一
int left=0, right=nums.length-1;
// 二分当前区间
while(left<=right){
// 中间位置
int mid=(left+right)/2;
// 如果中间位置的数小于等于区间最右边的数
// 那么[mid, right]是合理排序区间
if(nums[mid]<=nums[right]){
// 如果target不在该合理区间内，查询区间更改为另外半个区间
if(target<nums[mid]||target>nums[right]){
right=mid-1;
continue;
}
}
// 如果中间位置的数大于等于区间最左边的数
// 那么[left, mid]是合理排序区间
else if(nums[mid]>=nums[left]){
// 如果target不在该合理区间内，查询区间更改为另外半个区间
if(target<nums[left]||target>nums[mid]){
left=mid+1;
continue;
}
}
// 确保target在当前合理排序区间内时，开始常规二分查找
if(nums[mid]==target) return mid;
if(nums[mid]>target) right=mid-1;
else left=mid+1;
}
return -1;
} 本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array.
Memory Usage: 40.7 MB, less than 5.66% of Java online submissions for Search in Rotated Sorted Array.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-33-search-in-rotated-sorted-array-解题思路分析/