- 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}
- 题目给定一个排序数组，还有一个目标值，要直接想到用二分查找来解题
- 只不过题目增加了条件，如果找到值返回其索引，如果没有找到的话，需要返回它按顺序插入的位置 start
constsearchInsert=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}}returnstart}
- 时间复杂度：O(logn)
- 空间复杂度：O(1)