DSA Binary Search

Binary search finds a value in a sorted list by cutting the search area in half at every step. A list of one million items needs only about 20 checks. Linear search would need up to one million checks for the same job.

Think about opening a printed dictionary to find the word "mango". You flip to the middle and see "jelly". Mango comes later in the alphabet, so you ignore the first half entirely. You repeat the move on the second half until you land on the word. Binary search follows that exact habit.

The Sorted Data Rule

Binary search works only on sorted data. Each comparison tells the program which half to discard. An unsorted list gives no such hint, and the method returns wrong answers.

The Steps

• Set a low marker at the first item and a high marker at the last item.
• Find the middle position between them.
• Compare the middle value with the target.
• Move the low marker up when the middle value is too small, or move the high marker down when it is too big.
• Stop when the target appears or the markers cross.

Basic Code

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

numbers = [3, 8, 14, 21, 27, 35, 42]
print(binary_search(numbers, 27))   # 4

Target = 27
Index:   0   1   2   3   4   5   6
Value:  [3,  8, 14, 21, 27, 35, 42]
         L           M           H     mid = 21 (index 3), too small
                     L   M       H     mid = 35 (index 5), too big
                     L,M,H             mid = 27 (index 4), found

Why It Is So Fast

n = 1,000,000
after step 1  -> 500,000 left
after step 2  -> 250,000 left
after step 3  -> 125,000 left
...
after step 20 -> about 1 left

The number of steps equals log base 2 of n, written as O(log n).

Variation: First Occurrence

A sorted list may hold repeated values. This version keeps searching left after a match to find the earliest position.

def first_index(items, target):
    low, high = 0, len(items) - 1
    answer = -1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            answer = mid
            high = mid - 1
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return answer

print(first_index([1, 2, 2, 2, 3], 2))   # 1

Variation: Search on the Answer

Binary search can find a number that satisfies a rule, even without a list. The integer square root of 30 is the largest whole number whose square stays at or below 30.

def int_sqrt(n):
    low, high = 0, n
    answer = 0
    while low <= high:
        mid = (low + high) // 2
        if mid * mid <= n:
            answer = mid
            low = mid + 1
        else:
            high = mid - 1
    return answer

print(int_sqrt(30))   # 5

Each guess either fits the rule or breaks it, and that yes-or-no answer drives the halving.

Real-Life Uses

Phone contact lists jump to a name without scanning every entry. Version control tools hunt for the exact change that broke a program by halving the history. Game servers find a player rank inside a sorted leaderboard. Apps that ask "what is the smallest size that fits?" often search over possible sizes this way.

Common Mistakes

Using high = len(items) with a low <= high loop reads past the end of the list. Forgetting the +1 or -1 when moving a marker creates an endless loop. Running the method on unsorted data gives unreliable results. Test with a list of one item, two items, and a missing target to catch these slips.

Binary Search vs Linear Search

Linear search checks items one by one and works on any list, sorted or not. Binary search needs sorted data and wins on large lists. Sorting an unsorted list first costs O(n log n), so a single lookup may not justify the sort. Many lookups on the same list justify it easily.

Complexity Summary

• Time: O(log n)
• Space: O(1) for the loop version
• Requirement: sorted data

Key Points

• Binary search halves the search area at every step.
• The data must stay sorted.
• The loop ends when the markers cross.
• Variations find first or last positions among duplicates.
• The same idea solves "find the best value that works" problems.