Binary Search Algorithm Explained (With Code)

Quick Answer

Binary search finds a target in a sorted array by repeatedly checking the middle element and discarding the half that cannot contain it. It needs sorted input and runs in O(log n) time, which makes it far faster than checking every item. Use the iterative version by default; in real Python code, the built-in bisect module does the same job.

What Is the Binary Search Algorithm?

The binary search algorithm is a fast way to find a value inside a sorted list. Instead of checking every item one by one, it looks at the middle element, decides whether the target must be in the left half or the right half, and throws away the half that cannot contain it. Every step cuts the remaining items in half, so even a list of a million numbers is searched in about 20 steps.

Compare that with linear search, which walks through the list from start to end. For a million items, linear search may need a million comparisons; binary search needs roughly 20. That gap is the whole reason binary search matters, and it is one of the first algorithms you will meet in any coding interview or DSA course.

Why It Only Works on Sorted Data

Binary search only works if the input is already sorted. The entire trick depends on one fact: if the middle element is smaller than your target, the target (if it exists) must be to the right; if the middle is larger, the target must be to the left. That decision is only valid when the data is in order.

If the array is not sorted, the "throw away half" step becomes a blind guess, and you can skip right past the value you are looking for. So the rule is simple:

No sorting, no binary search. If your data is unsorted, either sort it first or use linear search.

Sorting itself costs time, usually O(n log n). So binary search pays off when you search the same sorted list many times, not when you sort once just to do a single lookup.

The Low, High, and Mid Logic

Binary search tracks the part of the array still worth checking using two pointers, low and high. low is the first index that could hold the target and high is the last. The middle index is mid = (low + high) // 2.

Each step does one comparison at mid:

• If arr[mid] equals the target, you found it, so return mid.
• If arr[mid] is less than the target, the answer is to the right, so move low = mid + 1.
• If arr[mid] is greater than the target, the answer is to the left, so move high = mid - 1.

The loop keeps going while low <= high. When low crosses past high, the range is empty and the target is not in the array. Here is a trace searching for 23 in a 10-element array:

Array:  [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Index:   0  1  2   3   4   5   6   7   8   9

Step 1: low=0, high=9, mid=4  arr[4]=16 < 23  go right, low=5
Step 2: low=5, high=9, mid=7  arr[7]=56 > 23  go left,  high=6
Step 3: low=5, high=6, mid=5  arr[5]=23 = 23  found at index 5

Three comparisons for ten items, and it would take at most four even in the worst case.

Iterative Binary Search in Python

The iterative version uses a while loop and no extra memory. This is the version most people should reach for by default.

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


numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))   # 5
print(binary_search(numbers, 100))  # -1

The function returns the index where the target sits, or -1 when it is not present. Returning an index is more useful than returning True/False, because you often need the position, not just a yes-or-no answer.

Recursive Binary Search in Python

The recursive version expresses the same idea by calling itself on the smaller half. It reads closely to the definition of the algorithm, which some learners find clearer.

def binary_search(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    else:
        return binary_search(arr, target, low, mid - 1)


numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 72))  # 8
print(binary_search(numbers, 7))   # -1

The low and high parameters have defaults, so you can still call it as binary_search(arr, target). The base case low > high stops the recursion when the range is empty.

Time and Space Complexity: O(log n)

Because every step halves the search space, the number of steps grows very slowly. For n items, the worst case is about log₂ n comparisons, which is O(log n) time. The table below shows how much work each approach does in the worst case:

For space, the iterative version is O(1): it uses a fixed amount of memory no matter how big the array is. The recursive version is O(log n), because each call adds a frame to the call stack until the recursion unwinds.

Common Gotchas and Bugs

Binary search is famously easy to get slightly wrong. Watch out for these:

• Forgetting to sort. Running binary search on unsorted data returns wrong answers silently, with no error, just garbage.
• Wrong loop condition. It must be while low <= high, not <. Using a plain < skips the case where the target sits at the last remaining index.
• Off-by-one updates. Always move to mid + 1 or mid - 1, never back to plain mid. Setting low = mid can loop forever.
• Integer overflow in other languages. In Python, integers never overflow, so (low + high) // 2 is safe. In Java, C++, or Go, prefer low + (high - low) // 2 to avoid overflow on very large indices.

If you remember only one thing: test with a target that is the first element, the last element, a middle element, and one that is missing. Those four cases catch almost every bug.

When to Use It (and Our Recommendation)

Reach for binary search when your data is sorted (or worth sorting once) and you will search it repeatedly. Good real-world fits include looking up a word in a dictionary, finding a record by ID, or Python's standard-library bisect module, which is a production-ready binary search.

Our recommendation: learn to write the iterative version from memory. It uses O(1) space, has no recursion limit, and is what interviewers expect. Use the recursive version to understand the idea, and use Python's built-in bisect in real projects instead of rewriting the logic yourself.

import bisect

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
i = bisect.bisect_left(numbers, 23)
print(i, numbers[i] == 23)  # 5 True

Want to practise algorithms like this with guided, hands-on exercises? Our free Python course takes you from the basics to data structures and searching, one clear step at a time.

Frequently Asked Questions