Binary Search Explained: Python, Java, and Interview Patterns

Binary search can find any element in a sorted array of 1 billion items in at most 30 comparisons. Linear search could take up to 1 billion. That is the power of O(log n) and why binary search is one of the most tested algorithms in coding interviews. The prerequisite: the array must be sorted and support O(1) random access.

This article covers how binary search works with a step-by-step dry run, iterative and recursive implementations in Python, Java, and C++, complexity analysis, the mid-index overflow bug, and the interview patterns that separate strong candidates from average ones.

Key Takeaways

What Is Binary Search?

What is binary search?

Binary search is a divide-and-conquer search algorithm that works on sorted arrays. It compares the target value to the middle element of the array, then discards half the search space based on whether the target is smaller or larger. This halving continues until the target is found or the search space is empty. Two prerequisites: the data must be sorted, and you must be able to access any element in O(1) time (arrays work; linked lists do not).

When can you use binary search?

There are two key instances when you can use binary search:

• The data structure is sorted or monotonic: any sequence where you can say ‘everything to the left satisfies condition X, everything to the right does not’ qualifies.
• You can access any element in O(1) time: binary search requires jumping to the middle, which is instant in an array but O(n) in a linked list, eliminating the speedup.

How Binary Search Works

How does binary search work step by step?

The following steps are executed when running the binary search:

1. Set a low pointer to index 0 and a high pointer to the last index.
2. Find the mid index: mid = low + (high – low) / 2.
3. Compare arr[mid] to the target. If equal, return mid. If target is less, set high = mid – 1. If target is greater, set low = mid + 1.
4. Repeat until low is greater than high (target not found) or target is found.

Dry run: Array [3, 7, 11, 14, 20, 28, 35, 42, 50, 61], Target = 28

Binary Search Algorithm Steps

What are the steps of the binary search algorithm?

The following are the steps of the binary search algorithm:

1. Initialise low = 0 and high = length – 1.
2. While low <= high: calculate mid = low + (high – low) / 2.
3. If arr[mid] equals target: return mid.
4. If arr[mid] is less than target: set low = mid + 1.
5. If arr[mid] is greater than target: set high = mid – 1.
6. If the loop ends without finding target: return -1.

Binary Search Pseudocode

Iterative pseudocode (use mid = low + (high – low) / 2 to prevent overflow)

binarySearch(arr, target):
  low = 0, high = len(arr) - 1
  while low <= high:
    mid = low + (high - low) / 2    // prevents integer overflow
    if arr[mid] == target: return mid
    else if arr[mid] < target: low = mid + 1
    else: high = mid - 1
  return -1

Binary Search Code

How do you implement binary search in Python?

Iterative – Python

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

Recursive – Python

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

How do you implement binary search in Java?

Iterative – Java

static int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

How do you implement binary search in C++?

Iterative – C++

int binarySearch(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

Iterative vs Recursive Binary Search

What is the difference between iterative and recursive binary search?

Binary Search Time and Space Complexity

What is the time complexity of binary search?

The Mid-Index Overflow Bug

Why should you write mid = low + (high – low) / 2 instead of mid = (low + high) / 2?

When low and high are both large integers, for example when they are both close to INT_MAX in a 32-bit system, the expression low + high overflows. In Java and C++ this wraps to a negative number, producing an invalid index. The form low + (high – low) / 2 is always safe because high minus low is always non-negative and smaller than either value alone. This bug was present in Java’s standard library binary search implementation until it was corrected in 2006. It is a documented FAANG interview question at Google and Meta.

Binary Search vs Linear Search

How does binary search compare to linear search?

Binary Search Interview Patterns

In which interview problem patterns does binary search appear?

Binary search is a recurring pattern across multiple interview problem categories. The key insight for advanced patterns: binary search applies to any search space with a monotonic condition, not just sorted arrays.

Conclusion

Binary search is O(log n), requires a sorted array, and is the most efficient general-purpose search algorithm. Understanding the mid overflow bug, the iterative vs recursive tradeoff, and the binary search on answer pattern separates candidates who have used binary search from those who truly understand it. For structured preparation, many candidates explore a FAANG interview preparation program to strengthen problem-solving and coding interview skills systematically.

FAQs: Binary Search

Q1. What is the prerequisite for binary search?

The data structure must be sorted and must support O(1) random access. Arrays satisfy both. Linked lists do not: finding the middle element requires O(n) traversal, which eliminates the logarithmic advantage entirely.

Q2. Why does binary search not work on linked lists?

Binary search requires O(1) access to the middle element. In a linked list, finding the middle element requires O(n) traversal. This makes the combined complexity O(n log n), which is worse than linear search at O(n). Use linear search on linked lists, or sort the list and convert to an array first.

Q3. Is binary search stable?

Stability is a concept for sorting algorithms, not search algorithms. Binary search is deterministic: if the array has duplicate values it will find one occurrence but does not guarantee which one. To find the first or last occurrence of a value in an array with duplicates, use the first/last occurrence variant shown in the interview patterns table above.

Q4. What is the difference between binary search and a binary search tree?

Binary search is an algorithm applied to a sorted array. A binary search tree (BST) is a data structure where every node satisfies the BST property. Both achieve O(log n) search on average, but they operate on different data structures: binary search on a sorted array, BST traversal on a tree structure via pointer navigation.

Recommended Reads:

• Binary Insertion Sort
• Data Structures and Algorithms: AVL Trees
• Insertion Sort Algorithm
• Difference Between Recursion and Iteration
• Recursion in Data Structures: Definition, Examples, and How It Works