【数据结构与算法】(9):二分查找


字数:764 阅读时长:3分钟 阅读:85

二分查找 也是比较常见的一个算法,本文就分别使用 循环递归 的形式实现二分查找。

数据结构与算法 · 二分查找

一、问题描述

给定一个可排序的数组,找到其中值为 targetindex 位置。

示例 1:

  • 输入:[1,2,3,4,5,6,7,8,9] , target=7
  • 输出:c

示例 1:

  • 输入:[300, 400, 500, 600, 700, 800, 900] , target=500
  • 输出:2

二、代码演示

  1. 二分查找 循环,性能更好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}
  1. 二分查找 递归,代码更清晰更简洁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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万次 的查找测试。

1
2
3
4
5
6
7
8
9
10
11
12
13
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')





binarySearch1 run time: 0


binarySearch2 run time: 0


通过运行得知二分查找 循环递归 的执行效率相差无几。但是 循环 形式的二分查找避免了函数的多次调用,因此更胜一筹。

四、总结

  • 凡有序,必二分
  • 凡二分,时间复杂度必包含 O(logn)
  • 都可以使用递归和循环

《数据结构与算法》系列

  1. 什么是算法复杂度
  2. 堆(heap)、栈(stack)、队列(queue)
  3. 把一个数组旋转k步
  4. 判断字符串是否括号匹配
  5. 数组、栈、链表、队列结构与对比
  6. 用两个栈实现一个队列
  7. 反转单向链表
  8. 用链表实现队列
  9. 二分查找
  10. 查找两数之和

欢迎访问:天问博客

本文作者: Tiven
发布时间: 2023-07-17
最后更新: 2023-07-20
本文标题: 【数据结构与算法】(9):二分查找
本文链接: https://www.tiven.cn/p/5aae9ba7/
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处!
欢迎留言,提问 ^_^
个人邮箱: tw.email@qq.com
notification icon
博客有更新,将会发送通知给您!