二分查找 也是比较常见的一个算法，本文就分别使用 循环 和 递归 的形式实现二分查找。
一、问题描述
给定一个可排序的数组，找到其中值为 target 的 index 位置。
示例 1：
- 输入：
[1,2,3,4,5,6,7,8,9] , target=7
- 输出：
c
示例 1：
- 输入：
[300, 400, 500, 600, 700, 800, 900] , target=500
- 输出：
2
二、代码演示
- 二分查找 循环，性能更好
function binarySearch1(arr: number[], target: number):number {
const len = arr.length;
if (len === 0) return -1;
let startIndex = 0;
let endIndex = len - 1;
while (startIndex <= endIndex) {
const midIndex = Math.floor((startIndex + endIndex) / 2);
const midValue = arr[midIndex]
if (target < midValue) {
// 目标值较小，在左侧继续查找
endIndex = midIndex - 1;
} else if (target > midValue) {
// 目标值较大，在右侧继续查找
startIndex = midIndex + 1;
} else {
// 相等
return midIndex;
}
}
return -1;
}
- 二分查找 递归，代码更清晰更简洁
function binarySearch2(arr: number[], target: number, startIndex?: number, endIndex?: number):number {
const len = arr.length;
if (len === 0) return -1;
if (startIndex == null) startIndex = 0
if (endIndex == null) endIndex = len - 1
if (startIndex > endIndex) return -1
const midIndex = Math.floor((startIndex + endIndex) / 2)
const midValue = arr[midIndex]
if (target < midValue) {
// 目标值较小，在左侧继续查找
return binarySearch2(arr, target, startIndex, midIndex -1)
} else if (target > midValue) {
// 目标值较大，在右侧继续查找
return binarySearch2(arr, target, midIndex + 1, endIndex)
} else {
// 相等
return midIndex
}
}
三、性能测试
分别用 循环 和 递归 二分查找的方法，对 [10, 20, 30, 40, 50, 60] ; target=20 ，进行 100万次 的查找测试。
let arr2 = [10, 20, 30, 40, 50, 60]
console.time('binarySearch1')
for (let i = 0; i < 100 * 10000; i++) {
binarySearch1(arr2, 20)
}
console.timeEnd('binarySearch1')
console.time('binarySearch2')
for (let i = 0; i < 100 * 10000; i++) {
binarySearch2(arr2, 20)
}
console.timeEnd('binarySearch2')
let startIndex = 0;
let endIndex = len - 1;
while (startIndex <= endIndex) {
const midIndex = Math.floor((startIndex + endIndex) / 2);
const midValue = arr[midIndex]
if (target < midValue) {
// 目标值较小，在左侧继续查找
endIndex = midIndex - 1;
} else if (target > midValue) {
// 目标值较大，在右侧继续查找
startIndex = midIndex + 1;
} else {
// 相等
return midIndex;
}
}
return -1;
}
// 二分查找 递归
function binarySearch2(arr, target, startIndex, endIndex) {
const len = arr.length;
if (len === 0) return -1;
if (startIndex == null) startIndex = 0
if (endIndex == null) endIndex = len - 1
if (startIndex > endIndex) return -1
const midIndex = Math.floor((startIndex + endIndex) / 2)
const midValue = arr[midIndex]
if (target < midValue) {
// 目标值较小，在左侧继续查找
return binarySearch2(arr, target, startIndex, midIndex -1)
} else if (target > midValue) {
// 目标值较大，在右侧继续查找
return binarySearch2(arr, target, midIndex + 1, endIndex)
} else {
// 相等
return midIndex
}
}
let arr2 = [10, 20, 30, 40, 50, 60]
function run() {
let s1 = performance.now()
for (let i = 0; i < 100 * 10000; i++) {
binarySearch1(arr2, 20)
}
document.querySelector('.box1-ms').innerText = performance.now() - s1 + ' ms'
let s2 = performance.now()
for (let i = 0; i < 100 * 10000; i++) {
binarySearch2(arr2, 20)
}
document.querySelector('.box2-ms').innerText = performance.now() - s2 + ' ms'
}
通过运行得知二分查找 循环 和 递归 的执行效率相差无几。但是 循环 形式的二分查找避免了函数的多次调用，因此更胜一筹。
四、总结
- 凡有序，必二分
- 凡二分，时间复杂度必包含
O(logn)
- 都可以使用递归和循环
《数据结构与算法》系列
- 什么是算法复杂度
- 堆(heap)、栈(stack)、队列(queue)
- 把一个数组旋转k步
- 判断字符串是否括号匹配
- 数组、栈、链表、队列结构与对比
- 用两个栈实现一个队列
- 反转单向链表
- 用链表实现队列
- 二分查找
- 查找两数之和
欢迎访问：天问博客
