Count 1's in a Sorted Binary Array

Count 1's in a Sorted Binary Array looks trivial — but it is a clean lesson in turning "count something" into "find a boundary," and then attacking that boundary with binary search instead of a linear scan.

The slow way first

The obvious idea: walk the array from the left and count 1s until you hit a 0. That works and is O(n) — fine for a small array, but it ignores the gift the problem hands us. The array is sorted: all the 1s are bunched on the left and all the 0s on the right. Whenever data is sorted, a linear scan is usually leaving speed on the table.

The key reframe: the number of 1s is exactly the index of the first 0 (the spot where 1 flips to 0). So we do not need to count anything — we just need to locate that 1→0 boundary.

The idea: binary-search the boundary

Finding the first 0 in a sorted array is a textbook binary search. Keep a window [lo, hi] and a running answer boundary (start it past the end, as if no 0 exists yet). Look at the middle:

• If a[mid] == 0, this 0 might be the first one — record boundary = mid, then search left for an even earlier 0.
• If a[mid] == 1, the first 0 must be to the right — move lo past mid.

When the window is empty, boundary holds the index of the leftmost 0, which is the count of 1s.

The trick is that finding a[mid] == 0 does not stop the search — a later 0 is never the answer, but an earlier one might be, so we keep shrinking toward the left edge of the zeros.

Walk through it

Step through the animation on [1, 1, 1, 1, 0, 0, 0]. The pointers lo and hi bound the part still in play; mid is the cell we test. Each time we see a 1, the left half (dimmed) is discarded. Each time we see a 0, we record the boundary and hunt left. The search converges on index 4 — the first 0 — and that index, 4, is the count of 1s.

Pseudocode

lo, hi = 0, len(a) - 1
boundary = len(a)              # index of first 0, assume none yet
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] == 0:
        boundary = mid          # candidate first 0; look further left
        hi = mid - 1
    else:                       # a[mid] == 1
        lo = mid + 1            # first 0 is to the right
return boundary                 # = number of 1s

The Python solution

def count_ones(a):
    lo, hi = 0, len(a) - 1
    boundary = len(a)
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == 0:
            boundary = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return boundary

• boundary starts at len(a) — if the array were all 1s, no 0 is ever found and the answer is the full length.
• mid = (lo + hi) // 2 picks the middle of the live window.
• Lines 6–8 are the heart: a 0 at mid is a candidate first 0, so we save it and push hi left to look for an earlier one.
• The else branch handles a 1 at mid: the first 0 is strictly to the right, so lo = mid + 1.
• When the loop ends, boundary is the index of the leftmost 0, which equals the number of 1s.

Complexity

We turn an O(n) count into an O(log n) boundary search using only a constant amount of extra space. The win grows with the array: a million elements take about 20 comparisons instead of up to a million.

When this pattern shows up

Practice