Binary Search

Problem

Problem from greatfrontend.com

Implement a function that performs binary search on an array of numbers. The function should take in a sorted array of integers and a target integer to find. It returns the index of the target element or -1, if the target element doesn't exist in the array.

Examples

binarySearch([1, 2, 3, 6, 9, 11], 6) // 3

binarySearch([1, 2, 3, 12, 16, 14], 5) // -1

Recap

Binary search is a search algorithm that can efficiently determine if a sorted array of integers contain a specific number. The algorithm repeatedly divides the input array into half until the target element is found, thereby decreasing the search space by half each step. It is a significant improvement versus linear search.

Here is a quick explanation of how binary search works on an array that is already sorted:

1. Calculate the middle index of the array and retrieve the middle element.
2. If the target element is greater than the middle element, search the right half of the array (ignore the left half).
3. If the target element is lesser than the middle element, search the left half of the array.
4. If the target element is equal to the middle element, return the index of the element.
5. Repeat the steps above until we complete the search. Return -1 if the target was not found.

My Solution

Iterative:

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

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

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

  return -1
}

Recursive:

export default function binarySearch(arr, target) {
  return binarySearchImpl(arr, target, 0, arr.length - 1)
}

function binarySearchImpl(arr, target, left, right) {
  if (left > right) {
    return -1
  }

  const mid = Math.floor((left + right) / 2)

  if (target < arr[mid]) {
    return binarySearchImpl(arr, target, left, mid - 1)
  }

  if (target > arr[mid]) {
    return binarySearchImpl(arr, target, mid + 1, right)
  }

  return mid
}