Binary Search & Search Spaces

Logarithmic search algorithms: preventing integer overflow (left + (right - left) // 2), boundary invariants, searching rotated arrays, and binary search on monotonic answer spaces.

The Binary Search Principle

Binary search finds the position of a target value within a sorted array by repeatedly halving the active search interval.

Definition: Logarithmic Search

By eliminating half of the search space at each comparison, an array of size N is searched in at most floor(log2(N)) + 1 steps.

Mid Calculation Without Integer Overflow

mid = left + (right - left) // 2

Variable Definitions & Term Breakdown:

(left + right) // 2Can overflow 32-bit signed integers in C++/Java when left + right > 2^31 - 1

left + (right - left) // 2Mathematically identical and numerically safe

Canonical Binary Search Template

The standard closed-interval [left, right] template with strict boundary updates.

1def binary_search(nums, target):
2    left, right = 0, len(nums) - 1
3    
4    while left <= right:
5        mid = left + (right - left) // 2
6        if nums[mid] == target:
7            return mid
8        elif nums[mid] < target:
9            left = mid + 1
10        else:
11            right = mid - 1
12            
13    return -1
14 
15arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
16idx = binary_search(arr, 23)
17print(f"Target 23 found at index: {idx}")