Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Classic Binary Search
DSA

Classic Binary Search

Understand the standard binary search algorithm for finding elements in sorted data.

Binary Search finds an element in a sorted array by repeatedly cutting the search range in half — O(log n).

Focus on recognizing:

Sorted + Search → Binary Search

Core Template

public int binarySearch(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return -1;
}
def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1
int binarySearch(vector<int>& nums, int target) {
    int lo = 0;
    int hi = (int)nums.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }

    return -1;
}
function binarySearch(nums, target) {
  let lo = 0,
    hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);

    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1;
}

Compare → eliminate half → repeat. Each probe halves the range.

Compare with mid → discard half → repeat.

Pattern 1: First Occurrence

Watch [1,3,5,7,9,11] collapse to three probes to find 7. Press ▶ to animate.

Classic Binary Search (Iterative)

Find a target in a sorted array by repeatedly halving the search range with lo and hi pointers. O(log n) time, no recursion.

Array [1,3,5,7,9,11], target 7. Compare mid: < target → discard left half (lo=mid+1); > target → discard right half (hi=mid-1); == target → found. The blue excluded region shows what's already thrown away each step.

BINARY SEARCH VISUALIZER
Steps –
1
0
3
1
5
2
7
3
9
4
11
5
Target: 7
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        lo = 0, hi = n - 1
                      
                        2
                        while lo <= hi:
                      
                        3
                          mid = (lo + hi) / 2   // round down
                      
                        4
                          if nums[mid] == target: return mid
                      
                        5
                          if nums[mid] < target: lo = mid + 1
                      
                        6
                          else:                  hi = mid - 1
                      
                        7
                        return -1

With duplicates, don’t return immediately — record the match and keep searching left:

public int firstOccurrence(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;
    int result = -1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) {
            result = mid;      // candidate
            hi = mid - 1;      // keep searching left
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return result;
}
def first_occurrence(nums, target):
    lo, hi = 0, len(nums) - 1
    result = -1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            result = mid       # candidate
            hi = mid - 1       # keep searching left
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return result
int firstOccurrence(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    int result = -1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) {
            result = mid;      // candidate
            hi = mid - 1;      // keep searching left
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return result;
}
function firstOccurrence(nums, target) {
  let lo = 0,
    hi = nums.length - 1,
    result = -1;

  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);

    if (nums[mid] === target) {
      result = mid; // candidate
      hi = mid - 1; // keep searching left
    } else if (nums[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return result;
}

First = Match → Save → Go Left

Pattern 2: Last Occurrence

Mirror image — save and search right:

Last Occurrence

Find the last occurrence of a target in a sorted array. Bias binary search right on equality — keep searching in the right half.

Array: [1,2,2,2,3], target=2. On match at mid=2, don't stop — search right for a later occurrence. Found at index 3.

ARRAY VISUALIZER
Steps –
1
0
2
1
2
2
2
3
3
4
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        lo = 0, hi = n - 1, result = -1
                      
                        2
                        while lo <= hi:
                      
                        3
                          mid = (lo + hi) / 2
                      
                        4
                          if nums[mid] == target: result = mid; lo = mid + 1
                      
                        5
                          else if nums[mid] < target: lo = mid + 1
                      
                        6
                          else: hi = mid - 1
                      
                        7
                        return result
                      
public int lastOccurrence(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;
    int result = -1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) {
            result = mid;      // candidate
            lo = mid + 1;      // keep searching right
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return result;
}
def last_occurrence(nums, target):
    lo, hi = 0, len(nums) - 1
    result = -1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            result = mid       # candidate
            lo = mid + 1       # keep searching right
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return result
int lastOccurrence(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    int result = -1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) {
            result = mid;      // candidate
            lo = mid + 1;      // keep searching right
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return result;
}
function lastOccurrence(nums, target) {
  let lo = 0,
    hi = nums.length - 1,
    result = -1;

  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);

    if (nums[mid] === target) {
      result = mid; // candidate
      lo = mid + 1; // keep searching right
    } else if (nums[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return result;
}

Last = Match → Save → Go Right · For boundaries in general, see Lower & Upper Bound.

Common Mistakes

Integer overflow in mid.

mid = lo + (hi − lo) / 2 — (lo + hi) / 2 can overflow in Java/C++.

Wrong loop condition.

while (lo <= hi) for this template; lo < hi belongs to boundary templates that keep hi = mid.

Returning immediately on duplicates.

First/last occurrence need the save-and-continue dance, not an instant return mid.

Unsorted input.

The halving logic is only valid on a sorted search space.

Complexity

OperationTime
SearchO(log n)
SpaceO(1)

My Private Notes

Notes are auto-saved locally to this device.