33.搜索旋转排序数组

就只想到了O(n)的， 想到的二分，

target<nums[left] 则在右边有序搜索target>=nums[left],在左边有序搜素自然是错误的，于是搁置不得了之。

看了题解恍然大悟。 以mid分成左右两个数组。 其中至少一个是有序的，且范围已知

如果target在此范围内，二分即可不在此范围内，搜索另一个数组 class Solution { public int search(int[] nums, int target) { return searchHelp(nums,target,0,nums.length-1); } private int searchHelp(int[] nums,int target,int left,int right){ if(left>right) return -1; int mid=left+((right-left)>>1); if(nums[mid]==target) return mid; if(mid-1>=left&&nums[left]<=nums[mid-1]){ //有序在左边，且目标值在里面 if(target>=nums[left]&&target<=nums[mid-1]){ right=mid-1; while (left<=right){ mid=left+(right-left)/2; if(nums[mid]==target) return mid; if(nums[mid]>target) right=mid-1; else left=mid+1; } }//不在里面，搜索右边无序的。 return searchHelp(nums,target,mid+1,right); }else { //有序在右边，且目标在里面 if(mid+1<nums.length&&target<=nums[right]&&target>=nums[mid+1]){ left=mid+1; while (left<=right){ mid=left+(right-left)/2; if(nums[mid]==target) return mid; if(nums[mid]>target) right=mid-1; else left=mid+1; } } return searchHelp(nums,target,left,mid-1); } } }

还有一种更简洁的写法

class Solution { public int search(int[] nums, int target) { int left=0; int right=nums.length-1; while (left<=right){ int mid=left+((right-left)>>1); if(nums[mid]==target) return mid; if(mid-1>=left&&nums[left]<=nums[mid-1]){ if(target<=nums[mid-1]&&target>=nums[left]){ right=mid-1; }else left=mid+1; }else{ if(mid+1<nums.length&&target>=nums[mid+1]&&target<=nums[right]){ left=mid+1; } else right=mid-1; } } return -1; } }

关于判断

if(mid-1>=left&&nums[left]<=nums[mid-1]){ nums[left]<=nums[mid-1] 取等号，是为了考虑只有一个数的时候