算法是一组完成任务的指令，任何代码片段都可视为算法。

二分查找

---

什么是二分查找

二分查找是一种算法，其输入的是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置，负责返回null。

假设要在电话簿中查找一个名字K打头或O打头的人，可以从A打头的部分开始查询，但更合乎逻辑的做法是从中间开始查找。解决这类问题可以通过二分查找。

例如：在0 - 100中，查找某个数的位置，最佳方法是按照50，75 这种方式去询问。

对于一个包含n个元素的列表，用二分查找最多需要 （log2 n） 步，而简单查找（遍历）最多需要n步。

因为我想乘此机会实战使用python，所以这个系列的文章中所有算法都会用JavaScript与python各实现一遍。

JavaScript 实现：

// 在一个有序的数组中（数组每个值等于其下标），从中搜索出目标数字。
const length = 1000000;
const list = Array.from({ length }).map((current, index) => index); // 创建数组
const target = Math.floor(Math.random() * length); // 创建目标数字

// 简单查找，按照下标一次循环遍历，输出最后的值
function simpleLookup(list, target) {
  const length = list.length;
  for(let i = 0; i < length; i++) {
    if(list[i] === target) return `simpleLookup ${list[i]}`
  }
  return false;
}

// 二分查找
function binarySearch(list, target) {
  let low = 0; // 最小的下标
  let high = list.length - 1; // 最大的下标
  while(low <= high) { // 判断条件，缩小至只包含一个元素
    let mid = Math.floor((low + high) / 2); // 中间下标
    let guess = list[mid]; // 中间下标的实际值
    if(guess === target)  return `binarySearch ${guess}`;
    else if(guess > target)  high = mid - 1; //  猜的数字大了，调小high
    else  low = mid + 1; // 猜的数字小了，调大low
  }
  return false;
}

console.time('simpleLookup');
simpleLookup(list, target);
console.timeEnd('simpleLookup');

console.time('binarySearch');
binarySearch(list, target);
console.timeEnd('binarySearch');

// 环境： node.js v10.4.1
// target 461672
// simpleLookup: 2.244ms
// binarySearch: 0.192ms
复制代码

例子的最后我放了一次我的运行结果，可以看到效率有显著提升，感兴趣的同学，自己也可以测试一下效果。

python实现：

import random

# python中直接实现二分查找算法
# python规范不喜欢驼峰命名，那就用下划线咯
def binary_search(list, target):
  low = 0 # 最小的下标
  high = len(list) - 1 # 最大的下标
  while low <= high: # 判断条件，缩小至只包含一个元素
    # // 地板除号，只取整数部分，就是向下取整
    mid = (low + high) // 2 # // 中间下标
    guess = list[mid]
    if guess == target:
      return mid
    if guess > target:
      high = mid - 1 # 猜的数字大了，调小high
    else 
      low = mid + 1 # 猜的数字小了，调大low

list = range(0,100)
a = random.randint(0,99)
print(binary_search(list, a))
复制代码

大O表示法

---

大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

简单查询，需要检查每个元素，因此需要执行n次操作，最多猜测的次数与列表长度相同，这被称为线性时间，使用大O表示法，这个运行时间就是O(n)。

而二分查找需要执行 log n 次，大O表示法为O(log n)。