二分查找

将元素对半查找，快速将查找范围缩小一半。

先决条件：

• 必须是有序的数据，元素按照关键字有序排列
• 必须是顺序存储结构， 链表无法实现。

/**
 * 二分查找实现
 * @param {Array} data 数组
 * @param {String,Number} search 查找的内容
 */
function binSearch(data, search) {
  // data 为数组

  if (!Array.isArray(data)) return;
  let right = data.length;
  let left = 0;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (data[mid] < search) left = mid + 1;
    else if (data[mid] > search) right = mid - 1;
    else return mid;
  }
  return -1;
}

const data = [1, 2, 3, 4, 6, 8, 10, 15, 39, 100, 105, 110, 200];

console.log(binSearch(data, 5));
// 结果：-1

console.log(binSearch(data, 6));
// 结果：4