30秒学会 JavaScript 片段 – Binary search

Finds the index of a given element in a sorted array using the binary search algorithm.

• Declare the left and right search boundaries, l and r, initialized to 0 and the length of the array respectively.
• Use a while loop to repeatedly narrow down the search subarray, using Math.floor() to cut it in half.
• Return the index of the element if found, otherwise return -1.

[!NOTE]

Does not account for duplicate values in the array.

代码实现

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

翻译自：https://www.30secondsofcode.org/js/s/binary-search