Binary Search

First PublishedFeb 11, 2026ByAtif Alam

Difficulty: Easy. ROI: Medium.

Other common names: Binary search on the answer (for search-space use).

When to use: Use when the array (or range) is sorted and you need to find a value, first/last occurrence, or the smallest value that satisfies a condition. Also “binary search on the answer” when the answer is in a range and you can test feasibility.

How Binary Search is different than Two Pointers:

The two indices only mark the range; the decision is always at the middle (you compare arr[mid] to the target, not the two ends).
Each step discards half the range — that’s why you get O(log n). Two pointers typically move one step at a time (O(n)).
Binary search finds a single value (or first/last occurrence, or “smallest x such that …”). Two pointers work with pairs or two active positions (e.g. two numbers that sum to target).
In short: binary search uses “two indices as bounds” and always inspects the middle; two pointers use two indices as the active positions and move them one step at a time.

Idea: Maintain a range [lo, hi] that must contain the answer. Each step compare the middle element to the target (or test mid for feasibility) and narrow the range to the left or right half.

Time / space: O(log n) time, O(1) extra space.

Example #1 — Find Target in Sorted Array

Sample input and output

1
arr = [1, 3, 5, 7, 9]
2
print(binary_search(arr, 5))   # True
3
print(binary_search(arr, 4))   # False

Sample input: arr = [1, 3, 5, 7, 9], target = 5.
Sample output: True — 5 is in the array. For target = 4 the output is False (not in array).

Code (with inline comments)

1
def binary_search(arr, target):
2
    lo, hi = 0, len(arr) - 1   # range that could contain the answer
3

4
    while lo <= hi:
5
        mid = (lo + hi) // 2   # middle index (integer division)
6
        if arr[mid] == target:
7
            return True
8
        if arr[mid] < target:
9
            lo = mid + 1   # target must be in the right half
10
        else:
11
            hi = mid - 1   # target must be in the left half
12
    return False

Line-by-line:

lo, hi = 0, len(arr) - 1 — We keep a range [lo, hi] (inclusive) where the target could be. Initially the whole array.
while lo <= hi: — If lo passes hi, the range is empty and the target isn’t in the array.
mid = (lo + hi) // 2 — Integer division (//) gives a whole number. We check the middle element of the current range.
if arr[mid] == target: return True — Found it.
if arr[mid] < target: lo = mid + 1 — The array is sorted, so if the middle value is smaller than the target, the target must be to the right. We shrink the range to [mid+1, hi].
else: hi = mid - 1 — The middle value is greater than the target, so the target must be to the left. We shrink to [lo, mid-1].
return False — The loop ended without finding the target.

Execution trace (numbered list)

For arr = [1, 3, 5, 7, 9], target = 5:

Step 1: lo=0, hi=4, mid=2, arr[mid]=5. 5 == 5 → return True.

For a miss (e.g. target=4): Step 1: lo=0, hi=4, mid=2, 5>4 → hi=1. Step 2: lo=0, hi=1, mid=0, 1<4 → lo=1. Step 3: lo=1, hi=1, mid=1, 3<4 → lo=2. lo>hi → return False.

Execution trace (code with step comments)

1
arr = [1, 3, 5, 7, 9]
2
target = 5
3
lo, hi = 0, len(arr) - 1   # 0, 4
4

5
# Step 1
6
mid = (lo + hi) // 2   # 2
7
# arr[2] == 5 == target → return True

For target=4: mid=2, 5>4 → hi=1; mid=0, 1<4 → lo=1; mid=1, 3<4 → lo=2; lo>hi → return False.

Execution trace (ASCII diagram)

Range [lo, hi] and mid at each step; ^ marks mid.

1
arr = [ 1,  3,  5,  7,  9 ], target = 5
2
        lo      mid     hi
3
        [-------^-------]
4
        arr[mid]=5 == 5 → return True