Linear and binary search

Search

Linear search — O(n)

Goes through the array element by element until it finds the target. It works with any array, sorted or not.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

Binary search — O(log n)

Much faster, but it requires a sorted array. The idea: look at the middle and discard the half that cannot contain the target, then repeat.

function binarySearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) start = mid + 1;
    else end = mid - 1;
  }
  return -1;
}

With a million elements, linear search may make a million comparisons; binary search, only about 20.

Examples

Binary search step by step

function binarySearch(arr, target) {
  let start = 0, end = arr.length - 1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    console.log("Checking index", mid, "value", arr[mid]);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) start = mid + 1;
    else end = mid - 1;
  }
  return -1;
}
console.log("Found at:", binarySearch([1, 3, 5, 7, 9, 11], 9));