JavaScript 的 二分搜索实现

等级 5421 次按键

binarySearch 每一步检查中间元素并把范围减半,从而在有序数组中查找值。查找7输出3,查找不存在的8输出-1,查找1输出0。

JavaScript 代码

// 返回 target 在有序数组 arr 中的下标,找不到则返回 -1
1function binarySearch(arr, target) {
// 搜索范围一开始是整个数组:下标0到 length - 1
2 let left = 0;
3 let right = arr.length - 1;
4
// 只要范围内至少还有一个元素就继续循环
5 while (left <= right) {
// 中间元素的下标,向下取整
6 const mid = Math.floor((left + right) / 2);
7
// 中间元素就是 target:返回它的下标
8 if (arr[mid] === target) return mid;
// 中间值太小,target 只可能在右半部分
9 if (arr[mid] < target) left = mid + 1;
// 中间值太大,因此在左半部分继续查找
10 else right = mid - 1;
11 }
12
// 范围已为空:数组中没有 target
13 return -1;
14}
15
// 二分查找只适用于像这样的有序数组
16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
// 7 在第一次取中间时(下标3)就找到,输出3
17console.log(binarySearch(sorted, 7));
// 8 不在数组中,输出 -1
18console.log(binarySearch(sorted, 8));
// 1 是第一个元素,输出0
19console.log(binarySearch(sorted, 1));

运行结果

3
-1
0
用这段代码练习打字

可以用这段代码练习打字。成绩不会计入排行榜。

这段代码中的符号

这段 JavaScript 代码中需要输入的符号及其出现次数。

  • (× 12
  • )× 12
  • ,× 11
  • ;× 11
  • =× 10
  • .× 5
  • -× 3
  • [× 3
  • ]× 3
  • {× 2

JavaScript 等级 5 的更多代码示例

← 返回 JavaScript 打字练习