Binary Search Algorithm Explained: A Step-by-Step Guide for Beginners

Quick answer: Binary search finds a target value in a sorted array by repeatedly halving the search range. Keep two pointers, low and high; look at the middle element; if it equals the target you are done, if it is larger search the left half, if it is smaller search the right half. Each step discards half the remaining elements, so the algorithm runs in O(log N) time — about 20 comparisons for a million items, versus up to a million for a linear scan.

Binary search is the first “clever” algorithm most programmers learn, and it is still asked in interviews at every level because it is deceptively easy to get slightly wrong. In this guide you will see the problem statement with examples, a step-by-step walkthrough of how the search narrows down, a complexity comparison with linear search, complete iterative and recursive code in Python and C++, the off-by-one traps that cause infinite loops, and the common variants that build on the basic idea.

Problem statement

You are given a sorted array arr of size N and an integer K. Return the index (0-based) at which K is present. If K is not in the array, return −1.

Example 1

Input: N = 5, arr = {1, 2, 3, 4, 5}, K = 4
Output: 3
The value 4 sits at index 3.

Example 2

Input: N = 5, arr = {14, 24, 33, 35, 51}, K = 48
Output: −1
48 is not in the array.

Why not just scan the array?

A linear search checks every element from left to right until it finds K. On a sorted array that wastes information: if the middle element is 33 and you are looking for 48, every element to the left of the middle is also less than 48 and can be skipped entirely. Binary search exploits exactly this. The trade-off is simple — the array must be sorted first. If you only need to search once, sorting (O(N log N)) plus binary search costs more than a plain scan; if you search many times, sorting once pays for itself quickly.

How binary search works, step by step

1. Set low = 0 and high = N − 1. These mark the current search window.
2. While low <= high:
   • Compute mid = low + (high − low) / 2 (integer division).
   • If arr[mid] == K, return mid.
   • If arr[mid] > K, the target must be to the left: set high = mid − 1.
   • If arr[mid] < K, the target must be to the right: set low = mid + 1.
3. If the loop exits, the window is empty and K is absent: return −1.

Dry run on Example 1

arr = {1, 2, 3, 4, 5}, K = 4.

• low = 0, high = 4, mid = 2. arr[2] = 3 < 4, so low = 3.
• low = 3, high = 4, mid = 3. arr[3] = 4 == K. Return 3.

Two comparisons instead of four.

Dry run on Example 2

arr = {14, 24, 33, 35, 51}, K = 48.

• low = 0, high = 4, mid = 2. arr[2] = 33 < 48, so low = 3.
• low = 3, high = 4, mid = 3. arr[3] = 35 < 48, so low = 4.
• low = 4, high = 4, mid = 4. arr[4] = 51 > 48, so high = 3.
• Now low = 4 > high = 3. Loop ends. Return −1.

Complexity comparison

The O(log N) bound comes from halving: after k steps the window has N / 2^k elements, which reaches 1 when k = log₂ N.

Working code in Python

def binary_search(arr: list[int], k: int) -> int:
    """Iterative binary search. Returns index of k or -1."""
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == k:
            return mid
        if arr[mid] > k:
            high = mid - 1
        else:
            low = mid + 1
    return -1


def binary_search_recursive(arr: list[int], k: int, low: int, high: int) -> int:
    """Recursive version. Call with low=0, high=len(arr)-1."""
    if low > high:
        return -1
    mid = low + (high - low) // 2
    if arr[mid] == k:
        return mid
    if arr[mid] > k:
        return binary_search_recursive(arr, k, low, mid - 1)
    return binary_search_recursive(arr, k, mid + 1, high)


if __name__ == "__main__":
    print(binary_search([1, 2, 3, 4, 5], 4))                 # 3
    print(binary_search([14, 24, 33, 35, 51], 48))           # -1
    print(binary_search_recursive([14, 24, 33, 35, 51], 35, 0, 4))  # 3
    print(binary_search([], 7))                              # -1 (empty array)

In day-to-day Python you would often reach for the standard library’s bisect module: bisect.bisect_left(arr, k) returns the insertion point, and you check arr[i] == k to confirm presence. Knowing how to write it by hand is still essential for interviews and for the variants below.

Working code in C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int binarysearch(const vector<int>& arr, int k) {
        int low = 0;
        int high = static_cast<int>(arr.size()) - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;   // avoids overflow of low + high
            if (arr[mid] == k) return mid;
            if (arr[mid] > k)  high = mid - 1;
            else               low  = mid + 1;
        }
        return -1;
    }
};

int main() {
    Solution s;
    vector<int> arr1 = {1, 2, 3, 4, 5};
    vector<int> arr2 = {14, 24, 33, 35, 51};

    cout << "Example 1 Output: " << s.binarysearch(arr1, 4)  << endl;  // 3
    cout << "Example 2 Output: " << s.binarysearch(arr2, 48) << endl;  // -1

    // Standard library equivalent
    auto it = lower_bound(arr1.begin(), arr1.end(), 4);
    cout << "lower_bound index: " << (it - arr1.begin()) << endl;    // 3
    return 0;
}

C++ offers std::binary_search (returns a bool), std::lower_bound and std::upper_bound in <algorithm>. Java has Arrays.binarySearch().

Variants you will meet next

The same halving idea powers a whole family of problems. Once the basic version is solid, practise these:

• First or last occurrence of K when duplicates exist — do not return on equality; record the index and keep narrowing.
• Lower bound / upper bound — the smallest index with arr[i] >= K or arr[i] > K. This is what bisect_left and lower_bound compute.
• Search in a rotated sorted array — decide which half is sorted before choosing a direction.
• Binary search on the answer — when the answer itself is a number in a monotonic range (minimum capacity, maximum pages, square root), search that range instead of an array.

Binary search also pairs naturally with array problems you may have already seen, such as finding the missing number in a sorted array, where it reduces an O(N) scan to O(log N).

Common mistakes and pitfalls

1. Running it on an unsorted array. The result is meaningless. If the data is not sorted, sort it first or use a hash set.
2. Using low < high instead of low <= high. When the window shrinks to one element, the loop exits without checking it and you miss targets at the edges.
3. Setting high = mid or low = mid. Without the ±1 the window may never shrink, and the loop runs forever.
4. Computing mid = (low + high) / 2 in C++ or Java. For arrays with billions of elements the sum overflows a 32-bit int. Use low + (high − low) / 2. (Python integers do not overflow, but the habit is worth keeping.)
5. Returning the wrong thing on failure. The problem asks for −1; some variants ask for the insertion point. Read the statement.
6. Deep recursion on huge inputs. The recursive version is elegant but uses O(log N) stack; the iterative version is what you should write in production.

Frequently asked questions

Why is binary search O(log N)?

Each comparison discards half of the remaining elements. Starting from N elements, you can halve at most log₂ N times before reaching a single element, so the loop runs at most log₂ N + 1 times.

Does binary search work on a linked list?

Not efficiently. Binary search needs O(1) random access to the middle element; a linked list requires O(N) to reach the middle, destroying the advantage. Use it on arrays, vectors, or anything indexable.

What if the array is sorted in descending order?

Flip the two comparisons: move high left when arr[mid] < K and low right when arr[mid] > K. The structure is otherwise identical.

Iterative or recursive — which should I use in an interview?

Write the iterative version by default: no stack overhead, easier to adapt into the lower-bound and first-occurrence variants. Mention that a recursive version exists and explain its O(log N) stack cost.

Key takeaways

• Binary search requires a sorted array and finds a target in O(log N) by halving the search window each step.
• Use low <= high as the loop condition and mid ± 1 when moving the pointers to avoid infinite loops and missed edges.
• Compute mid = low + (high − low) / 2 to prevent integer overflow in C++ and Java.
• Prefer the iterative form; know bisect, lower_bound and Arrays.binarySearch for real projects.
• Master the basic version, then move on to first/last occurrence, rotated arrays and “binary search on the answer”.

Binary search is one of a handful of algorithms you must be able to write from memory in any interview. Our Interview Preparation program takes you through searching, sorting, recursion, dynamic programming and system design with mock interviews and mentor feedback. Prefer video walkthroughs? Follow along on our YouTube channel.