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

33. 搜索旋转排序数组

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; } }

Tags:

You may also like...

1 Response

Leave a Reply

Your email address will not be published. Required fields are marked *