【数据结构与算法】(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

二、代码演示

二分查找循环，性能更好

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

<div> <button style='padding: 10px 20px; color: #00b1fb;' class='rotate-btn' onclick='run()'>运行</button> <br> <b>binarySearch1 run time：</b> <span style='color: red;' class='box1-ms'>0</span> <hr> <b>binarySearch2 run time：</b> <span style='color: red;' class='box2-ms'>0</span> <hr> </div> <script> // 二分查找循环 function binarySearch1(arr, target) { 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, 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'

} </script>

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

四、总结

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

《数据结构与算法》系列

欢迎访问：天问博客