二分查找
二分查找是最基础的查找算法，它的时间复杂度为 O(logn)。虽然二分查找的思想简单直白，但是写二分查找的时候在处理边界条件的时候会写错。这里给出一种处理边界条件的时候不容易写错的二分查找模板。参考视频讲解 (opens in a new tab)
function search(nums: number[], target: number): number {
function binarySearch(l: number, r: number): number {
while (l + 1 !== r) {
const mid = Math.floor((l + r) / 2);
const tmp = nums[mid];
if (tmp > target) {
r = mid;
} else if (tmp < target) {
l = mid;
} else {
return mid;
}
}
return -1;
}
// 这里必须是 -1 和 nums.length
return binarySearch(-1, nums.length);
}