二分查找 理解

[sailei1]

'use strict';

function binary_search(list, item) {
  let low = 0;
  let high = list.length - 1;
  debugger;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    let guess = list[mid];
    if (guess === item) {
      return mid;
    }
    if (guess > item) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return null;
}

let my_list = [1, 3, 5, 7, 9,10];

console.log(binary_search(my_list, 3)); // 1
console.log(binary_search(my_list, -1)); // null

前提：有序列表

思路：先粗调 然后再精调 1 从 0 开始 找到数组的长度 整个区间压缩1倍， 对比值 2 如果中间值大于查找值 再从整个区间压缩1倍， 对比值 如果中间值小于查找值， 把开始值扩大1倍 对比值 3 找到 中间值 等于查找值的 返回下标 如果在查找过程中 开始值大于此时整个区间值 说明轮询完了 没找到该元素