Binary Search

In this chapter you will learn the basics of binary search and how to apply it in a different problems.

Binary Search is an algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.

Problem

Given a sorted array of integers, write a function that returns the index of the target value. If the target value is not found, return -1.

Example

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let target = 5;

console.log(binarySearch(arr, target)); // 4

Solution

General structure

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Complexity Analysis

The time complexity of binary search is O(log n) where n is the number of elements in the array. The space complexity is O(1) since we are using only a constant amount of space.

Practice

• Search in Rotated Sorted Array
• Search in Rotated Sorted Array II
• Find Minimum in Rotated Sorted Array