二分法 | LeeZhian

二分法

Jul 28, 2022 ·

2 Min Read

它是一种查找的方法，每次排除一半进行查找。

优点：
- 大大减少查找的次数，数据越大越明显。
缺点：
- 查询的依赖条件必须是一个有序列表

举例：

大家都玩过一种猜数字的游戏，1-100看谁更快的猜出我心想的数字？

如果在不使用二分法，使用最傻瓜的方式就是，直接从1开始猜，顺序猜到100，如果我正好想的是100，则你要猜100次。时间复杂度O(n)

如果使用二分法，同样心想100，第一次我猜50，小了；第二次我猜75，小了；第三次我猜87，小了…最多我猜8次就猜到了。大大减少了查找的次数。时间复杂度O(log n)

代码实现：

// 代码写法可能不是最优雅的，但是原理是这样。
const result = 100

let start = 1 // 始值
let end = 100 // 末值
let guess = 0 // 猜的值

while(start < end) {
  let half =  (end - start) / 2
  half = half < 1 ? Math.ceil(half) : Math.floor(half)

  guess += half
  if(guess === result) {
    console.log('猜到了');
    return
  } else if(result > guess) {
    start = guess
  } else if(result < guess) {
    end = guess
  }
}

Last edited Feb 15