题目：
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -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
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
- 1 <= nums.length <= 5000
- -104 <= nums[i] <= 104
- nums 中的每个值都 独一无二
- 题目数据保证 nums 在预先未知的某个下标上进行了旋转
- -104 <= target <= 104
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
【二分查找】
参考:@【liweiwei1419】：https://leetcode.cn/problems/search-in-rotated-sorted-array/solution/er-fen-fa-python-dai-ma-java-dai-ma-by-liweiwei141/ 以及评论区的各位老师！
题目中说将数据进行旋转，这样的话就会将搜索区间从中间一分为二，位于中间的元素nums[mid]一定会在其中一个有序的区间中。由于数组中不存在重复元素，mid与左右两边的元素关系不是小于关系就是大于关系。这里就讨论mid与右边界的大小关系，分为两种情况：
1.mid的值严格大于右边界时：nums[mid] > nums[right]
- 此时在区间[left, mid – 1]内的元素一定是有序的，如果target在[left, mid]里，即nums[left] <= target <=nums[mid]，此时设置right = mid – 1;
- 上一个区间的反面，target在区间[mid, right]中，left == mid；
2.mid的值严格小于右边界时：nums[mid] < nums[right]
- 此时在区间[mid, right]内的元素一定是有序的，如果target在[mid, right]里，即nums[mid] <= target <=nums[right]，此时设置left = mid ;
- 上一个区间的反面，target在区间[left, mid – 1]中，right == mid – 1；
注意：这里的区间存在[mid, right]，为了防止区间只有两个元素的时候，向下取整会让mid一直和left相同，出现死循环，故需要变成向上取整mid = left + (right – left + 1) / 2。
java代码：
1 class Solution { 2 public int search(int[] nums, int target) { 3 int left = 0, right = nums.length - 1; 4 while (left < right){ 5 int mid = left + (right - left + 1) / 2; 6 if (target == nums[mid]) return mid; 7 //先根据nums[0]与target判断目标值在mid左端还是右端 8 //在右端,例如[6,7,1,2,3,4,5] 9 if(nums[mid] < nums[right]) { 10 if(target >= nums[mid] && target <= nums[right]){ 11 left = mid; 12 }else{ 13 right = mid - 1; 14 } 15 }else{ 16 //在前部分:[3,4,5,6,7,1,2] 17 if(target <= nums[mid - 1] && target >= nums[left]){ 18 right = mid - 1; 19 }else{ 20 left = mid; 21 } 22 } 23 } 24 //循环结束的条件：left == right 25 return nums[left] == target ? left : -1; 26 } 27 }
python3代码：
1 class Solution: 2 def search(self, nums: List[int], target: int) -> int: 3 left, right = 0, len(nums) - 1 4 while left <= right: 5 mid = left + (right - left) // 2 6 if nums[mid] == target: 7 return mid 8 # 右边有序 9 # [7,1,2,3,4,5,6] 10 # 取等号是有可能mid == right 11 if nums[mid] <= nums[right]: 12 if nums[mid] < target <= nums[right]: 13 left = mid + 1 14 else: 15 right = mid - 1 16 # 左边有序 17 # [3,4,5,6,7,1,2] 18 # 取等号是有可能mid == left 19 elif nums[mid] >= nums[left]: 20 if nums[left] <= target < nums[mid]: 21 right = mid - 1 22 else: 23 left = mid + 1 24 return -1
说明：
【向上取整】与【向下取整】
向上取整与向下取整主要是为了处理当只剩下两个元素的情况，这时 left 和 right 相差1。
向上取整：把整个区间划分成[left, mid -1] 和 [mid, right]，把mid划分给了右区间，如果操作是选择了包含mid的这个区间，那么就需要mid值来更新left，如果向下取整，left和right值算出来的mid就与left相等（例如:(4+5) / 2 == 4）,再将left更新成mid，相当于没有更新left，故需要向上取整，算出来的mid值与right相等，这样left向右移动，得到更新，和right指向相同的值。
向下取整：把整个区间划分成[left, mid] 和 [mid + 1, right]，把mid划分给了左区间，如果操作是选择了包含mid的这个区间，那么就需要mid值来更新right，如果向上取整，left和right值算出来的mid就与right相等（例如:(5 + 4) / 2 +1 == 5）,再将right更新成mid，相当于没有更新right，故需要向下取整，算出来的mid值与left相等，这样right向左移动，得到更新，和left指向相同的值。
总结：
mid如果被分给了右区间，需要向上取整，保证left能够被新值更新。
mid如果被分给了左区间，需要向上取整，保证left能够被新值更新。
原文地址：http://www.cnblogs.com/liu-myu/p/16908011.html
