Binary Search Pattern

The binary search technique is an algorithmic pattern used to efficiently locate an element, boundary, or optimal value within a sorted collection or monotonic search space. By repeatedly halving the search range based on a comparison, it drastically reduces search time.

Why use Binary Search?

Logarithmic Time Complexity: Reduces execution time from $O(n)$ linear scanning to $O(\log n)$ search efficiency.
Optimal Boundary Detection: Ideal for locating specific start/end positions, first occurrences, or extreme thresholds.
Implicit Search Spaces (Binary Search on Answer): Can find optimal answers without an explicit array when the solution space exhibits a monotonic property (e.g., if value $K$ is valid, all values $> K$ are also valid).

Common scenarios for Binary Search:

Finding exact target values or indices in sorted arrays.
Locating first/last occurrences or boundaries of duplicated elements.
Finding peak elements, local minima, or rotation points in modified arrays.
Finding square roots or mathematical functions within a range.
Optimizing resource allocation or capacity thresholds (Binary Search on Answer).

Binary Search Templates

When solving array, range, and optimization problems efficiently, binary search is applied using two core templates based on search space reduction and boundary conditions:

Template 1: Inclusive Boundary Search (while (left <= right))

In this template, right starts at n - 1, and the search space includes both bounds [left, right]. Every iteration updates search boundaries explicitly (left = mid + 1 or right = mid - 1).

Search Space: [left, right] (Inclusive at both ends).
Termination Condition: left > right (Search space is completely exhausted).
Common use cases: Exact target lookup, finding first and last occurrences of an element, and target-based range searches.

Template 2: Boundary / Predicate Convergence Search (while (left < right))

Here, the search space continuously shrinks until left and right converge on a single optimal index (left == right).

Search Space: [left, right) (Right boundary acts as a convergence wall).
Termination Condition: left == right (Points directly to the optimal boundary or peak element).
Common use cases: Finding minimum/maximum in rotated arrays, peak element detection, and Binary Search on Answer optimization problems.

In this template, right starts at n - 1, and the search space includes both bounds [left, right]. Every iteration updates search boundaries explicitly (left = mid + 1 or right = mid - 1).

In this template, the search space continuously shrinks until left and right converge on a single optimal index (left == right).

The “Find First and Last Position of Element in Sorted Array” problem is a classic binary search challenge where you are given a sorted array of integers and a target value. The goal is to find the first (leftmost) and last (rightmost) position of the target in the array and return their indices. If the target does not exist in the array, return [-1, -1].