二分查找

假设要在电话簿中找一个名字以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