题目描述查看：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
题目的意思是从一个位置颠倒有序数组，让它变成两部分有序，从这个两部分有序的数组中，找一个特定的值存不存在。题目要求的时间复杂度O(logn)，提醒我们用到二分查找。
-
思路
设定left，right，mid指针，对数组进行二分查找。
先判断mid落在哪个有序区间上，在看target在mid的左边还是右边。
如果mid比left值大，说明落在了颠倒位置的左边，即在左边有序位置进行二分查找即可。
1 if(nums[left] <= nums[mid]) { 2 if (nums[left] <= target && target < nums[mid]) right = mid - 1; 3 else 4 left = mid + 1; 5 }
如果mid比left值小，说明落在了右边的有序序列中，在右边的有序序列进行二分查找。
1 else { 2 if (target > nums[mid] && target <= nums[right]) left = mid + 1; 3 else 4 right = mid - 1; 5 }
-
边界条件
6行，while循环里的等号。当查找的值是left == right时，没有等号，不会执行循环里的if(nums[mid] == target)return mid，直接跳出循环返回-1，发生错误。
10行，14行的等号，由于left和right是mid+1得到的，下一次查找的范围应该是左边这一堆或者右边这一堆，需要包括nums[left]和nums[right]。
1 class Solution { 2 public int search(int[] nums, int target) { 3 if(nums.length == 0)return -1; 4 int left = 0; 5 int right = nums.length -1; 6 while (left <= right){ 7 int mid = left + (right - left) /2; 8 if(nums[mid] == target)return mid; 9 if(nums[left] <= nums[mid]) { 10 if (nums[left] <= target && target < nums[mid]) right = mid - 1; 11 else 12 left = mid + 1; 13 }else { 14 if (target > nums[mid] && target <= nums[right]) left = mid + 1; 15 else 16 right = mid - 1; 17 } 18 } 19 return -1; 20 } 21 }
-
二分查找模板
1 public static int search(int[] nums, int target) { 2 if(nums.length == 0){ 3 return -1; 4 } 5 int left = 0; 6 int right = nums.length -1; 7 while(left <= right){ 8 int mid = left + (right - left)/2; 9 if(target == nums[mid])return mid; 10 else if(target > nums[mid])left = mid +1; 11 else right = mid -1; 12 } 13 return -1; 14 }