Home / DSA / Lesson 6

Searching — linear and binary

Intermediate 8 min read Lesson 6 of 9

Linear search is O(n). Binary search is O(log n) comparisons on a sorted array. If the data is unsorted, sorting first is O(n log n) — then binary search only helps if you search many times.

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

(hi - lo) >> 1 avoids overflow in languages with fixed integers; in JS it is still a clear midpoint. The invariant: if the target exists, it is inside [lo, hi].

Judge: Binary search. Pattern: Binary search as a pattern.