Binary Search and How to Implement It

Binary search is an efficient way to search through a sorted array for a target value. It takes a divide and conquer approach, where we get the middle element of the array and create left and right side arrays without the middle element (divide). Then we’ll check to see if the target is less than or greater than the middle element, and if so, we’ll keep searching through the left half or right half, respectively, with each step effectively halving the number of elements to be looked at (conquer).

Time and Space Complexity

The time complexity of binary search is logarithmic at O(log n). We will look through only half of an increasingly smaller data set per step. To get a time complexity of less than O(n), we must avoid touching all n elements, which binary search accomplishes.

Space complexity will depend on how you implement your algorithm (recursively vs. iteratively and create new subarrays vs. searching in-place). Implementing a recursive algorithm can have a space complexity of O(n) or O(log n), depending on if new subarrays are created. Taking an iterative approach will result in O(1) space.

Recursive Approach | new subarrays, O(n) space

When I learned binary search, I got familiar with this approach first of creating new arrays as it was easy to remember and intuitive. However, the tradeoff for ease of simple implementation is additional space, which is a factor you’ll want to consider in any situation.

function binarySearch(array, target) {
  // set your base case for recursive functions
  // if the array is empty, we know the element is not present  
  if (array.length === 0) return false;

  let midIdx = Math.floor(array.length / 2);
  let midVal = array[midIdx];
  // subarrays should not include the middle element
  let leftArray = array.slice(0, midIdx);
  let rightArray = array.slice(midIdx + 1);

  // if target is less than midVal, target should be likely in
  // the left array (pass in leftArray to the recursive call)
  if (target < midVal) {
    return binarySearch(leftArray, target);
  // if target is greater than midVal, target should be likely 
  // in the right array (pass in rightArray to the recursive call)
  } else if (target > midVal) {
    return binarySearch(rightArray, target);
  } else {
    return true;
  }
}

Recursive Approach | in-place, O(log n) space

To be able to reference the original array’s indices and keep track of the pointers that will help form the left and right halves of the array, we’ll want to pass in additional arguments to the function called low and high. low’s default value should be set to 0, as it serves as the lowest index while high’s default value is the last index in the array. midIdx is the middle index that will be the “halving point” of the “subarrays”, and we'll compare the element at its index (midVal) to the target value to see if the values match, or if the target is greater or less than the middle value.

This method will cut the space complexity down to O(log n), which is due to its call stack.

function binarySearch(array, target, low=0, high=array.length-1) {
  // set your base case for recursive functions
  // if low is greater than high, that means we’ve gone through 
  // the array and target is not present
  if (low > high) return false;

  // add low + high and divide in half to get midIdx 
  let midIdx = Math.floor((low + high) / 2);
  let midVal = array[midIdx];

  // when passing in low and high arguments to the recursive call, 
  // be sure to exclude midIdx (b/c we've already looked at it)
  if (target < midVal) {
    return binarySearch(array, target, low, midIdx - 1);
  } else if (target > midVal) {
    return binarySearch(array, target, midIdx + 1, high);
  } else {
    return true;
  }
}

Iterative Approach | in-place, O(1) space

The iterative approach also requires keeping track of low and high variables that act as the left and right sides of the array, with midIdx acting as the halving point and where we’ll be checking to see if midVal is equal to, less than, or greater than the target.

Though a recursive function may be easier to implement, an iterative approach will result in a space complexity of O(1).

function binarySearch(arr, target) {
  // setting the low and high indices
  let low = 0;
  let high = arr.length - 1;

  // want to keep searching until at least one element 
  // exists in the array
  while (low <= high) {
    const midIdx = Math.floor((low + high) / 2);
    const midVal = arr[midIdx];

    // return true if target equals midVal
    if (target === midVal) {
      return true;
      // if target is less than midVal, reassign high to 
      // midIdx - 1 (bc we've already looked at midIdx)
    } else if (target < midVal) {
      high = midIdx - 1;
      // else, the target is in the second half of array so 
      // reassign low to midIdx + 1
    } else {
      low = midIdx + 1;
    }
  }
  return false;
}

Check out the resources below for more information on binary search. Happy coding!

Resources
Binary Search Algorithm - Interview Cake
Binary Search Algorithm - Wikipedia
Iterative and Recursive Binary Search Algorithm