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

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

一、问题描述

给定一个可排序的数组，找到其中值为 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

二、代码演示

1. 二分查找 循环，性能更好

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;
}

2. 二分查找 递归，代码更清晰更简洁

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')

运行


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 许可协议进行许可。转载请注明出处！