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

二分查找是搜索算法中的一种，用来搜索 有序数组

二分查找：是一种简单算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要

查找的元素包含在列表中，二分查找返回其位置；否则返回 null 。

Javascript ES6实现

/** 
 * 函数binarySearch接受一个有序数组和一个元素。 如果指定的元素包含在数组中， 这个
 函数将返回其位置。 你将跟踪要在其中查找的数组部分—— 开始时为整个数组。
*/
const binarySearch = (list, item) => {
  // 数组要查找的范围
  // low、high用于跟踪要在其中查找的列表部分
  let low = 0  
  let high = list.length - 1

  while(low <= high) { // 只要范围没有缩小到只包含一个元素
    const mid = Math.floor((low + high) / 2)
    const guess = list[mid] // 找到中间的元素

    if(guess === item) { // 找到元素
      return mid
    }
    if(guess > item) { // 猜测的数大了
      high = mid - 1
    } else {　// 猜测的数小了
      low = mid + 1
    }
  }

  return null
}

const myList = [1, 3, 5, 7, 9]

console.log(binarySearch(myList, 3))
console.log(binarySearch(myList, -1))

运行时间：

二分查找的运行时间为对数时间（或log时间）。

如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多

需猜32次。

即：２的７次方 = 100

简单查找时间是ｙ= ax 的线性方方程

所以很容易得出结论

随着元素数量的增加（ｘ增加），二分查找需要的时间（ｙ）并不多， 而简单查找需要的时间（ｙ）却很多。

为检查长度为n的列表，二分查找需要执行log n次操作。使用大O表示法，

这个运行时间怎么表示呢？O(log n)。一般而言，简单算法的大O表示法像下面这样

大O符号

大O符号中指定的算法的增长顺序

以下是一些最常用的 大O标记法 列表以及它们与不同大小输入数据的性能比较。

• O(log n)，也叫对数时间，这样的算法包括二分查找
• O(n)，也叫线性时间，这样的算法包括简单查找。
• O(n * log n)，这样的算法包括 快速排序 ——一种速度较快的 排序 算法。
• ,这样的算法包括 选择排序 ——一种速度较慢的排序算法
• O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法

小结

• 算法的速度指的并非时间，而是操作数的增速。
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
• 算法的运行时间用大O表示法表示。
• O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多

参考