二分查找

使用二分查找算法在已排序的数组中找到给定元素的索引。

  • 声明左边界和右边界的搜索范围,lr,分别初始化为 0 和数组的 length
  • 使用 while 循环来反复缩小搜索子数组,使用 Math.floor() 将其分成两半。
  • 如果找到元素,则返回其索引;否则返回 -1

[!NOTE]

不考虑数组中的重复值。

const binarySearch = (arr, item) => {
  let l = 0,
    r = arr.length - 1;
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    const guess = arr[mid];
    if (guess === item) return mid;
    if (guess > item) r = mid - 1;
    else l = mid + 1;
  }
  return -1;
};

binarySearch([1, 2, 3, 4, 5], 1); // 0
binarySearch([1, 2, 3, 4, 5], 5); // 4
binarySearch([1, 2, 3, 4, 5], 6); // -1