Engineering Fluency OS

Why This Matters

Finding things is one of the most common operations in computing. Looking up a user by ID, checking if a word is in a dictionary, finding the right record in a database — these are all search problems. A linear search checks every element one by one, which works but is slow for large datasets. A binary search eliminates half the possibilities with each comparison, turning a million-element search into just 20 steps.

The difference between O(n) and O(log n) is enormous at scale. If you have a million records, linear search might check all million. Binary search checks about 20. Understanding when and how to use binary search is one of the highest-leverage skills in algorithm design.

Define Terms

Visual Model

Sorted: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

16mid = 4

[2, 5, 8, 12]target < 16 → go left

[23, 38, 56, 72, 91]target > 16 → go right

5mid = 1

[8, 12]target > 5 → go right

8 foundindex 2

< 16

> 16

> 5

The full process at a glance. Click Start tour to walk through each step.

Binary search halves the search space each step. O(log n) on sorted data.

Code Example

Code

// LINEAR SEARCH — O(n)
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1; // not found
}

// BINARY SEARCH — O(log n), requires sorted array
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

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

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      left = mid + 1;   // target is in right half
    } else {
      right = mid - 1;  // target is in left half
    }
  }

  return -1; // not found
}

const sorted = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log(binarySearch(sorted, 23));  // 5 (index)
console.log(binarySearch(sorted, 50));  // -1 (not found)

// FINDING INSERTION POINT
function findInsertionPoint(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
}

console.log(findInsertionPoint(sorted, 20)); // 5
console.log(findInsertionPoint(sorted, 0));  // 0

Interactive Experiment

Try these exercises:

Count how many comparisons binary search makes for an array of 100 elements vs 1000 elements. Does it roughly double, or increase by a small constant?
What happens if you run binary search on an unsorted array? Try it and observe incorrect results.
Modify binary search to find the first occurrence of a duplicate value (e.g., finding the first 5 in [1, 3, 5, 5, 5, 8, 12]).
Implement a function that uses binary search to find the square root of a number (integer part only).

Quick Quiz

Coding Challenge

Binary Search

Write a function called `binarySearch` that takes a sorted array of numbers and a target number. Return the index of the target if found, or -1 if not found. You must use the binary search algorithm (not linear search or built-in methods like indexOf).

Loading editor...

Real-World Usage

Searching algorithms are fundamental to everyday software:

Databases: B-tree indexes use a form of binary search to locate records in O(log n) time, making SELECT * WHERE id = 12345 near-instant on billions of rows.
Autocomplete: As you type, the system searches a sorted dictionary to suggest completions. Binary search narrows candidates quickly.
Version control: git bisect uses binary search on your commit history to find the exact commit that introduced a bug.
Operating systems: File system directories, process lookup tables, and memory page tables all use sorted structures with binary search.
Game development: Collision detection often uses spatial search structures (like binary space partitioning) to avoid checking every object pair.

Searching Algorithms