一定要早日上岸鸭 · July 16, 2021 1

33. 搜索旋转排序数组

「二分」的本质是两段性,并非单调性。只要一段满足某个性质,另外一段不满足某个性质,就可以用「二分」。

class Solution { public int search(int[] nums, int target) { int N=nums.length; if (N == 0) return -1; if (N == 1) return nums[0] == target ? 0 : -1; int l = 0 , r = N-1; while(l<r){ int mid = l+r+1>>1; if(nums[mid]>=nums[0]) l = mid; else r = mid &#8211; 1; } if(target>=nums[0]){ l=0; } else{ l+=1; r = nums.length-1; } while(l<r){ int mid = l+r>>1; if(nums[mid]>=target) r = mid; else l = mid+1; } return nums[r] == target ? r : -1; } }