Binary Search

Problem:

Find the target element within a sorted array.

Concept:

Divide the array into 3 parts (left, middle and right). Check the middle element, if it is larger than the middle element, the target element should be hidden in right. Otherwise, it should be hit (the same value) or hidden in the left part.

Javascript code snippet:

function binarySearch(arr, target) {
  let start = 0
  let end = arr.length - 1
  while (start <= end) {
    let middle = Math.floor((start + end) / 2)
    if (arr[middle] < target) {
      // Search the right half
      start = middle + 1
    } else if (arr[middle] > target) {
      // Search the left half
      end = middle - 1
    } else if (arr[middle] === target) {
      // Found target
      return middle
    }
  }
  // Target not found
  return -1
}