2015
Jun
17

Binary Search 是一个很有效率的演算法,简单的应用可以用处理 list 的搜寻,找到 list 中的某一个 item , 搜寻方式为不断的对 list 剖半再剖半,直到你找到正确的 item 。

Binary Search 可以用在哪呢? 举例来说,假设天空中有 2 万颗星星,每个星星都有一个唯一的名字,我们该如何从 2 万颗星星中,搜寻到我要的那一颗呢,若是使用暴力破解 forloop 的方式来搜寻,平均要搜寻 1 万次才能找到我要的那颗; 若是使用 Binary Search ,则最慢只要 15 次就一定能够搜寻到我要的星星资料。

15 次 与 1万次的差别,从这个例子就能看出演算法的重要性!

猜数字游戏

接著就让我来介绍 Binary Search 如何运作,Binary Search 第一步就是要合理的去猜测一个 List 里最中间的数字,例如有一个 1 ~ 100 的猜数字游戏 ,如果你第一值猜 25 ,那么我会跟你说「高一点」,接著你可能会猜 81 ,然后我再跟你说「低一点」,所以答案就一定会在 26 ~ 80 之间,就像下图一样,红色区域是有可能的答案,而黑色区域是已经被排除的数字。

1
26
80
100

当你每次都猜最中间的数字(例如 1 ~ 100 中间是 50),就会将数字列表切成两个一样大的区块,这个做法可以一次排除一半错误的数字,例如我们已经知道答案在 26 ~ 80 之间,那么我下一次就可以猜 53 ( (26 + 80) / 2 ),若是我告诉你「再低一点」,那么你就会知道答案在 26 ~ 52 之间。

1
26
53
100

我们来看看猜数字游戏中的程式演算法,如果题目的答案是 1 ~ n 之间的数字,首先我们定义一个变数 min ,min 代表可能的答案中的最小值,再定义一个变数 max , max 代表可能的答案中的最大值。

演算法逻辑 如下:

1. 设定 min = 1,以及 max = n.
2. 取 min ~ max 的中间值 m。
3. 如果 m 是答案,那么程式就可以回值传,
4. 如果 m 小於答案,那么设定 min = m + 1,回到第 2 步
4. 如果 m 大於答案,那么设定 max = m - 1,回到第 2 步

实作阵列的 Binary Search

来试看看如果在一个已排序的 Array 中使用 Binary Search ,首先我们有 25 个由小到大排序过的质数如下。

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

假设我们想知道 67 是否为质数,这时只要在 primes 这个变数中搜寻看看是否存在 67 ,若是有在 Array 中找到 67 的 index ,那么就可以得知 67 是质数。

如果我们从 Array 最左边开始寻找,那么我们要比对 18 次,才能找到 67 ,这个搜寻方式是很普通的 linear search 。


Binary Search 会是一个更有效率的搜寻方式,这个 Array 中含有 25 个数字,Index 分别是从 0 ~ 24 ,使用上述所讲的演算法逻辑来猜数字。

1. 设定 min = 0, max = 24
2. 取得 index = 12 的值, number = 41
3. 41 < 67 , 设定 min = 13
4. 取得 index = 18, number = 61
5. 存在 61 ,所以 61 是质数

我们总共只猜了两次,第一次猜 index 12 , 第二次猜 index 18 ,就猜中了答案,这个搜寻方式远比 Linear search 快得多。

Binary Search source code

JavaScript: Binary Search
  1. function binarySearch(array, targetValue) {
  2. var min = 0, max = array.length - 1, guess, value;
  3. while(1) {
  4. if (max < min) break;
  5. guess = Math.floor((min + max)/2);
  6. value = array[guess];
  7. if (value === targetValue) {
  8. return guess;
  9. } else if (value > targetValue) {
  10. max = guess - 1;
  11. } else if (value < targetValue) {
  12. min = guess + 1;
  13. }
  14. }
  15. return -1;
  16. };
  17.  
  18. var primes = [
  19. 2, 3, 5, 7, 11,
  20. 13, 17, 19, 23, 29,
  21. 31, 37, 41, 43, 47,
  22. 53, 59, 61, 67, 71,
  23. 73, 79, 83, 89, 97];
  24.  
  25. var result = binarySearch(primes, 73);
  26. console.log(result);

相关文章


回應 (Leave a comment)