二分查找
假设要在电话簿中找一个名字以K打头的人，(现在谁还用电话簿!) 可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做，而 是从中间开始，因为你知道以K打头的名字在电话簿中间。
又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。
现在假设你登录Facebook。当你这样做时，Facebook必须核实你是 否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的 用户名为karlmageddon，Facebook可从以A打头的部分开始查找，但更合 乎逻辑的做法是从中间开始查找。
这是一个查找问题，在前述所有情况下，都可使用同一种算法来解 决问题，这种算法就是二分查找。
下面的示例说明了二分查找的工作原理。我随便想一个1~100的数字。
你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。 假设你从1开始依次往上猜。
1 (小了)
2 (小了)
...........
49(小了)
这是简单查找，更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99， 你得猜99次才能猜到!
更佳的查找方式
从 50 开始。
50 (小了，但排除了一半的数字!至此，你知道1~50都小了。接下来，你猜75。)
75 (大了，那余下的数字又排除了一半!使用二分查找时，你猜测的是中间的数字，从而每次都 将余下的数字排除一半。接下来，你猜63(50和75中间的数字)。)
100个元素-->50-->25-->13-->7-->4-->2-->1
不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次 猜测都将排除很多数字!
假设你要在字典中查找一个单词，而该字典包含240 000个单词， 你认为每种查找最多需要多少步?
答案是18步。
对于包含n个元素的列表，用二分查
找最多需要log2n步，而简单查找最多需要n步。
javascript实现二分查找
二分查找需要注意的是，只能用在有序列表里面，所以使用之前要确保数组内容是有序的。
/**
* 二分查找
* @param list - 数组
* @param item - 查找的值
*/
function binary_search(list, item) {
let low = 0
let high = list.length - 1
let mid, guess;
while (low <= high) {
mid = Math.floor((low + high) / 2); // 取中间的索引下标，如果是奇数则向下取整
guess = list[mid]; // 取中间的值
console.log(mid, guess)
if (guess == item) {
return mid // 猜对了
}
if (guess > item) {
high = mid - 1 // 猜大了
} else {
low = mid + 1 // 猜小了
}
}
return '没有元素'
}
// 数组
let arr = Array.from(Array(100), (item, index) => {
return index + 1
})
console.log(binary_search(['a', 'b', 'c', 'd', 'e', 'f'], 'd')) // 3
console.log(binary_search(['a', 'b', 'c', 'd', 'e', 'f'], 'g')) // 没有元素
console.log(binary_search(arr, 9)) // 8
运行时间
每次介绍算法时，我都将讨论其运行时间。一般而言，应选择效率最高的算 法，以最大限度地减少运行时间或占用空间。
回到前面的二分查找。使用它可节省多少时间呢?简单查找逐个地检查数 字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最 多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性 时间(linear time)。
二分查找则不同。如果列表包含100个元素，最多要猜7次;如果列表包含40亿个数字，最多 需猜32次。厉害吧?
所以二分查找的速度为 O(log n),也叫对数时间。
