Sorted Arrays — Binary Search, Two Pointers, Gaps

Once an array is sorted, a universe of techniques opens: binary search, two pointers, merging, duplicate scanning, and gap analysis. The skill is recognizing sorted structure even when disguised.

Why this shows up in the real world

Phone contacts are sorted so search autocomplete can binary search prefixes. Financial time series sorted by timestamp allow window queries with two pointers instead of scanning everything. Version-sorted package lists let package managers skip incompatible ranges quickly.

Core idea (explained for students)

If input is sorted, ask: can I maintain two indices moving monotonically? Can I answer existence with bisect_left/right? Can I merge with another sorted stream in linear time? If not sorted yet, sometimes sort once O(n log n) unlocks faster total time than repeated linear scans.

Try this in Python

import bisect

xs = [1, 3, 5, 5, 7]
print(bisect.bisect_left(xs, 5), bisect.bisect_right(xs, 5))

Common mistakes

• Assuming sorted when only partially sorted—verify invariant.
• Binary search off-by-one templates—pick one and memorize.
• Sorting when two-pointer on original unsorted with hash could be faster.

Key takeaways

• Sorted property is a free lunch for search.
• Learn Python bisect module idioms.
• Combine with duplicate handling patterns.