二分查找
实现
js
function binarySearch(nums, target) {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
let i = 0;
let j = nums.length - 1;
// 循环,当搜索区间为空时跳出(当 i > j 时为空)
while (i <= j) {
// 计算中点索引 m ,使用 parseInt() 向下取整
const m = parseInt(i + (j - i) / 2);
if (nums[m] < target)
// 此情况说明 target 在区间 [m+1, j] 中
i = m + 1;
else if (nums[m] > target)
// 此情况说明 target 在区间 [i, m-1] 中
j = m - 1;
else return m; // 找到目标元素,返回其索引
}
// 未找到目标元素,返回 -1
return -1;
}