https://leetcode-cn.com/problems/binary-search/
这道题一看就是用二分查找可以以最小的时间复杂度解决问题
我们定义头尾各一个指针,通过二分他们的中间位,需要注意的一点是不能用 (left+right)/2
去计算他们的中间位,这样有可能会导致number溢出最大值丢失精度
从题意可以理解出这个是升序的数组,所以我们只需要不断二分去取中间位,然后移动left和right就可以得出解了,需要注意的点是移动点之后要移动一位,不然有可能会导致死循环,有可能mid和left和right相等,这样就死循环了
function search(nums: number[], target: number): number {
let left = 0 ,right = nums.length - 1
while (left<=right) {
const mid = left + ((right - left) >>1)
if (nums[mid] >target) {
right=mid-1
} else if(nums[mid] < target){
left = mid+1
} else {
return mid
}
}
return -1
};
空间复杂度O(logn)
时间复杂度O(1)
根据一个大佬的公式写出来的代码
https://www.bilibili.com/video/BV1d54y1q7k7?spm_id_from=333.999.0.0
function search2(nums: number[], target: number): number {
let l = -1, r = nums.length;
while (l + 1 !== r) {
const mid = l + (r - l >> 1)
if (nums[mid] < target)
l = mid
else
r = mid
}
return nums[r] === target ? r : -1
};