See all coding puzzles and patterns here.

---

Algorithm Description

A binary search is a DFS algorithm on a sorted data structure. However, binary search is limited to traversal through one path of the data structure and will not traverse multiple paths. A binary search splits the data down the middle and evaluates some target against the middle element. If the middle element is "less than" the target, then the target must be in the latter half of the data structure (if the data is sorted in increasing order). If the middle element is "greater than" the target, then the target must be in the earlier half of the data structure. If the middle element is "equal to" the target, then the search stops.

For each iteration, if a sub-search is needed, the bounds of the new search must be changed based on the result of the comparison of the middle element and bounds of the prior iteration. If the search moves to the left, the right bound is moved to the previous middle element. If the search moves to the right, the left bound is moved to the previous middle element. If the next middle element is equal to the left or right bound or if there are no left or right halves to inspect, then the search is terminated.

In some cases, such as Find K Closest Elements, a terminal search even if the target is not found is still desired, as the search is being used to find the item closest to the target.

---

Performance Characteristics

In general, the technique has an auxiliary space complexity of $O(1)$ since just scalar reference to the left, right and middle are retained; and a runtime complexity of $O(log(n))$, where $n$ is the size of the search space (typically the length of an input array).

---

Example Implementation

def binary_search(arr, target):
    """
    Will return index of target if found; otherwise, will return None.
    """
    l = 0
    r = len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            l = mid + 1
        else:
            r = mid

---

Puzzles

Puzzle	Difficulty	External Link
Dot Product of Two Sparse Vectors	Medium	Leetcode 1570 (Premium)
Find First and Last Position of an Element in a Sorted Array	Medium	Leetcode 34
Find K Closest Elements	Medium	Leetcode 658
Find Peak Element	Medium	Leetcode 162