【题目】
顺序排列的数组，每个点值不同。以某个点进行旋转（其实就是前后两段交换位置），对旋转后数组搜索有无target，没有-1，有返回位置
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
Example 3:
Input: nums = [1], target = 0 Output: -1
【思路】
找到旋转点P，顺序排列，那第一个后项比前项小的就是旋转点
将其分为[0,P)和[P,nums.length)两段分别做二分查找
最后输出两段中返回值大的（-1/任意位置）
100%
【代码】
class Solution { public int search(int[] nums, int target) { int p=0; for(int i=1;i<nums.length;i++){ if(nums[i]<nums[i-1]) p=i; } return Math.max(bs(nums,target,0,p),bs(nums,target,p,nums.length)); } public int bs(int[] nums,int target,int left,int right){ while(left<right){ int mid=left+(right-left)/2; if(nums[mid]==target) return mid; else if(nums[mid]<target) left=mid+1; else if(nums[mid]>target) right=mid; } return -1; } }