JavaScript 的 二分搜索实现
等级 5421 次按键
binarySearch 每一步检查中间元素并把范围减半,从而在有序数组中查找值。查找7输出3,查找不存在的8输出-1,查找1输出0。
JavaScript 代码
// 返回 target 在有序数组 arr 中的下标,找不到则返回 -11function binarySearch(arr, target) { // 搜索范围一开始是整个数组:下标0到 length - 12 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 // 范围已为空:数组中没有 target13 return -1;14}15 // 二分查找只适用于像这样的有序数组16const sorted = [1, 3, 5, 7, 9, 11, 13, 15];// 7 在第一次取中间时(下标3)就找到,输出317console.log(binarySearch(sorted, 7));// 8 不在数组中,输出 -118console.log(binarySearch(sorted, 8));// 1 是第一个元素,输出019console.log(binarySearch(sorted, 1));运行结果
3 -1 0
可以用这段代码练习打字。成绩不会计入排行榜。
这段代码中的符号
这段 JavaScript 代码中需要输入的符号及其出现次数。
(× 12)× 12,× 11;× 11=× 10.× 5-× 3[× 3]× 3{× 2