Binary Search Algorithm — A Complete Tutorial

Binary Search is a classic and efficient algorithm for finding an element in a sorted array (or sorted structure). It works by repeatedly dividing the search interval in half until the target is found or the interval is empty. This tutorial explains the intuition, provides step-by-step walkthroughs, code implementations (iterative and recursive) in multiple languages, common variants, complexity analysis, applications, pitfalls, and practical tips.

Introduction

Binary Search leverages the fact that the input array is sorted. Instead of searching linearly, it eliminates half of the remaining elements at each comparison by comparing the target value with the middle element. This gives it a logarithmic time complexity, O(log n), making it extremely efficient for large sorted datasets.

Preconditions

• The array (or data structure) must be sorted in ascending (or descending) order. Standard binary search examples assume ascending order.
• Random access to elements (O(1) access by index) is assumed for arrays. For some data structures (like linked lists), standard binary search is not efficient.

How Binary Search Works — Intuition

1. Start with the entire array: low = 0, high = n – 1.
2. Find the middle index: mid = low + (high – low) / 2 (use this formula to avoid overflow).
3. Compare array[mid] with target:
   • If equal, return mid (target found).
   • If array[mid] < target, discard left half by setting low = mid + 1.
   • If array[mid] > target, discard right half by setting high = mid – 1.
4. Repeat until low > high (target not present) or found.

Binary Search — Steps (Iterative)

1. Initialize pointers: low = 0, high = n – 1.
2. While low <= high:
   1. Compute mid safely: mid = low + (high – low) / 2
   2. If arr[mid] == target → return mid
   3. If arr[mid] < target → low = mid + 1
   4. Else → high = mid – 1
3. If not found, return -1 (or another indicator).

Pseudocode

// Iterative binary search (array indexed from 0 to n-1)
function binarySearch(arr, n, target):
    low = 0
    high = n - 1
    while low <= high:
        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

Implementations

1) Iterative — C++

#include <iostream>
#include <vector>
using namespace std;

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

int main() {
    vector<int> arr = {2, 5, 8, 12, 16, 23, 38};
    int target = 16;
    int idx = binarySearchIterative(arr, target);
    if (idx != -1) cout << "Found at index " << idx << "\n";
    else cout << "Not found\n";
    return 0;
}

2) Recursive — Java

public class BinarySearch {
    public static int binarySearchRecursive(int[] arr, int low, int high, int target) {
        if (low > high) return -1;
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) return binarySearchRecursive(arr, mid + 1, high, target);
        else return binarySearchRecursive(arr, low, mid - 1, target);
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38};
        int target = 23;
        int idx = binarySearchRecursive(arr, 0, arr.length - 1, target);
        System.out.println(idx != -1 ? "Found at index " + idx : "Not found");
    }
}

3) 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

# Example
arr = [2, 5, 8, 12, 16, 23, 38]
print(binary_search(arr, 12))  # Output: 3

Variants & Common Use-Cases

• First (leftmost) occurrence in a sorted array with duplicates
• Last (rightmost) occurrence
• Find lower bound (first >= target) / upper bound (first > target)
• Search on functions/monotonic predicates (binary searching on answer space)
• Finding the insertion position in a sorted array

Finding the First Occurrence (Leftmost)

def first_occurrence(arr, target):
    low, high = 0, len(arr) - 1
    res = -1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            res = mid
            high = mid - 1   # continue searching left
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return res

Step-by-Step Example (Finding First Occurrence)

arr = [1, 2, 4, 4, 4, 6, 7], target = 4

1. low=0, high=6 → mid=3 → arr[3]=4 → res=3, high=2
2. low=0, high=2 → mid=1 → arr[1]=2 < 4 → low=2
3. low=2, high=2 → mid=2 → arr[2]=4 → res=2, high=1
4. low=2, high=1 → loop ends, return res=2 (leftmost index)

Time & Space Complexity

Applications

• Searching in sorted arrays, databases or indices
• Finding roots or inverses of monotonic functions (with discrete steps)
• Binary searching on the answer: e.g., minimum maximum capacity, allocation problems
• Computing bounds (lower_bound / upper_bound) in STL-like libraries
• Used in many algorithmic problems in competitive programming and interview questions

Common Pitfalls and Tips

• Overflow when computing mid: avoid (low + high) / 2 for large indices — use low + (high – low) / 2.
• Off-by-one errors for boundaries: ensure loops use low <= high for inclusive search or adjust accordingly for half-open intervals [low, high).
• Ensure array is sorted as expected. If descending order is used, flip comparisons or invert logic.
• When searching duplicates, decide whether you need any occurrence, first, or last — and adapt boundaries.
• For non-random-access structures (e.g., linked lists) binary search is not efficient; prefer other approaches or convert to random access if feasible.

Practical Example — Finding Insert Position (Lower Bound)

def lower_bound(arr, target):
    low, high = 0, len(arr)  # notice high = len(arr) -> [low, high)
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low  # position to insert target to keep array sorted

Example: arr=[1,3,5,7], target=4 → lower_bound returns index 2 (insert before 5)

When NOT to Use Binary Search

• Unsorted data — linear search or sorting plus binary search may be needed.
• Data structures without O(1) random access (singly linked list).
• When the cost of accessing middle elements is high compared to sequential checks.

Practice Problems

• Find first and last positions of an element in a sorted array
• Search in a rotated sorted array
• Square root (integer) using binary search
• Find minimum element in a rotated sorted array
• Partition-related problems (like allocation) solved with binary searching on answer

Conclusion

Binary Search is an essential algorithmic tool that provides logarithmic-time search on sorted collections. Beyond basic lookup, its variants and the concept of “binary searching on the answer” are widely used in algorithm design. Key takeaways:

• Always ensure data is sorted and use safe mid computation to avoid overflow.
• Understand boundary conditions carefully to avoid off-by-one bugs.
• Learn variants (first/last occurrence, lower_bound/upper_bound) — they are extremely useful.

If you’re preparing for interviews or competitive programming, implement both iterative and recursive versions, and practice several variants (first/last occurrence, lower_bound/upper_bound, rotated array search).

Happy learning! — This article mirrored the crisp, example-driven style commonly found on GeeksforGeeks.