是什么

二分查找： 是一种在有序数组中查找某一特定元素的搜索算法

思想

• 从数组的中间开始
• 大于中间则去右边查找， 小于中间则去左边查找
• 依次执行，直到最后

条件

• 有序数组
• 不适合太大或太小的数据

怎么用

function search(arr, target) {
  if (arr.length < 1) return -1;
  let lowIndex = 0;
  let highIndex = arr.length - 1;
  while (lowIndex <= highIndex) {
    const middleIndex = Math.floor((lowIndex + highIndex) / 2);
    if (target < arr[middleIndex]) {
      highIndex = middleIndex - 1;
    } else if (target > arr[middleIndex]) {
      lowIndex = middleIndex + 1;
    } else {
      return middleIndex;
    }
  }
  console.log(lowIndex, highIndex); // 3, 2
  return -1;
}

const arr = [1, 5, 10, 39, 99, 123];
const res = search(arr, 99);
console.log(res); // 4

算法复杂度O(logn)

场景

数据量适中的有序数组