假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
在自己想到这道题的时候有个问题，那就是查找的方法不熟悉，只知道dfs和bfs，各种方法的时间复杂度和空间复杂度不清楚，从今天开始刷查找方法。 首先时间复杂度O(long n)就是二分查找的时间复杂度，那么就用二分查找，可是有一个问题，那就是二分查找需要有序数组，所给的数知识部分有序，中间存在断层。 这里就有一个诀窍，那就是存在断层也不要紧，只需要保证在一定范围内的数是有序的即可。 所以这就要明白一个东西，如何找到有序部分？ 那接着要明白一个东西，排序数组被旋转后，一定会分为三部分，large部分，small部分，node ，再引入一个mid变量，large.size和small.size哪个大，mid就在哪部分，相等mid就在node处。 接着就是判断target在mid左侧还是mid右侧。 但是还有一种特殊情况，那就是small node large，small.size更大，和small node large，large.size更大，这两种情况都会让mid比nums[0]大。 注意这两者的区别， 前者node的值一定大于mid的值，所以需要left=mid+1 后者node的值一定小于mid的值，所以需要right=mid-1
class Solution { public int search(int[] nums, int target) { int length = nums.length; if (length == 0) { return -1; } int left = 0, right = length - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } //这说明旋转后大数都在左半部分， if (nums[mid] >= nums[0]) { if (nums[mid] > target && nums[0] <= target) { right = mid - 1; } else { left = mid + 1; } } else { //当旋转后，小数都在左半部分时候 if (nums[mid] < target && nums[length - 1] >= target) { left = mid + 1; } else { right = mid - 1; } } } return -1; } }