- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
二分查找
先来看下有序数组的二分查找。
constsearch=function(nums,target){letstart=0letend=nums.length-1while(start<=end){constmid=start+((end-start)>>1)if(nums[mid]===target)returnmidif(nums[mid]<target){start=mid+1}else{end=mid-1}}return-1}
- 再来明确，因为本题是旋转数组，我们无法直接根据
nums[mid]与target的关系来定位target是在mid的左边还是右边 - 需要分段处理，先比较
nums[mid]与nums[start]的大小，来定位mid在左边还是右边 - 继续定位
target，判断target在mid的左边还是右边，然后分别调整边界start和end
constsearch=function(nums,target){letstart=0letend=nums.length-1while(start<=end){constmid=start+((end-start)>>1)if(nums[mid]===target)returnmidif(nums[mid]>=nums[start]){if(target>=nums[start]&&target<nums[mid]){end=mid-1}else{start=mid+1}}else{if(target>nums[mid]&&target<=nums[end]){start=mid+1}else{end=mid-1}}}return-1}
- 时间复杂度：O(logn)
- 空间复杂度：O(1)