/

JavaScript Algorithms: Binary Search

JavaScript Algorithms: Binary Search

Binary search is an efficient algorithm used to search for an item in an ordered array or any other ordered data structure. It reduces the search space by half with each iteration, making it a highly optimized search algorithm.

To perform a binary search, follow these steps:

  1. Start with the ordered array and the item you need to search for.
  2. Calculate the middle index of the array by dividing the number of elements by 2.
  3. Compare the middle item with the item you are searching for.
  4. If the middle item is equal to the target item, return the index of the middle item.
  5. If the middle item is greater than the target item, discard the right part of the array and repeat the process with the left part.
  6. If the middle item is less than the target item, discard the left part of the array and repeat the process with the right part.
  7. Repeat steps 2-6 until the item is found or the search space is exhausted.
  8. If the item is not found, return null.

Binary search has a time complexity of O(log n), which means that the search time grows logarithmically with the size of the array.

Here is a possible implementation of the binary search algorithm in JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const binarySearch = (list, item) => {
  let low = 0;
  let high = list.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const guess = list[mid];

    if (guess === item) {
      return mid;
    }

    if (guess > item) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return null; // if not found
}

To use the binarySearch function, pass in the ordered list and the item you want to find. It will return the index of the item if it is found, and null if the item is not found.

Here are some examples of using the binarySearch function:

1
2
3
console.log(binarySearch([1, 2, 3, 4, 5], 1)); // 0
console.log(binarySearch([1, 2, 3, 4, 5], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5], 6)); // null

Binary search is a fundamental algorithm in computer science and is widely used in various applications. It offers a significant optimization compared to linear search for large datasets.

tags: [“binary search”, “algorithms”, “JavaScript”, “optimization”]