Binary Search

easy

Given a sorted array of integers and a target, return the index of the target or -1 if not found

Binary Search (Classic)

Key Insight

Compare mid with target. If target < mid, search left half. If target > mid, search right half.

Step 1Initialize Pointers
Target: 9
L
R
-1
0
0
1
3
2
5
3
9
4
12
5
Search space: [0..5]

Set left=0, right=5. Target is 9.

1 / 5

Learn the Pattern

Binary SearchEliminate half the search space each iteration by comparing the midpoint against a condition, reducing O(n) linear scans to O(log n).
Practice the Code

Step-by-Step Walkthrough: Binary Search (Classic)

Compare mid with target. If target < mid, search left half. If target > mid, search right half.

  1. Initialize Pointers

    Set left=0, right=5. Target is 9.

  2. First Mid Calculation

    mid=(0+5)/2=2, arr[2]=3. 3 < 9, search right half.

  3. Narrow to Right

    left=3, mid=(3+5)/2=4, arr[4]=9. Found!

  4. Target Found

    arr[4]=9 equals target. Return index 4.

  5. Why O(log n)

    Halved from 6→3→1. Only 2 comparisons for 6 elements.