Visualized DSA Strategies
Episode 8 Binary Search
▶ This video is coming to YouTube soon.
The complete guide to binary search for coding interviews, in C#. First the idea: halve the range with every look, the two templates (an exact value, and where a yes or no question flips), why the middle is lo + (hi − lo) / 2 (C# wraps lo + hi silently), what it saves, C#'s built-in tools, and five traps. Then nine types, each worked as a small problem in full: examples, the brute force animated beside the running line of code, the complete code, every line explained, and the binary search the same way.
What you'll learn
- How binary search halves the range, and why it's O(log n)
- The exact-value template: lo <= hi with mid ± 1
- The lower-bound template: lo < hi with hi = mid, for any question that flips once
- Why (lo + hi) / 2 wraps in C#, what checked and >>> do, and the safe middle
- Array.BinarySearch and List.BinarySearch, the ~ complement for a miss, SortedSet floor and ceiling
- First and last position with two lower bounds
- Rotated sorted arrays: the minimum, and search, by asking which half is sorted
- A sorted grid as one long line, and a peak without sorting
- Binary search on the answer, and searching a key's timestamps
Chapters
- 0:00Intro
- 0:25Halve the range
- 1:01A question that flips once
- 1:55Template 1: an exact value
- 3:01Template 2: where it flips
- 3:53The overflow bug
- 5:11What binary search saves
- 5:40Binary search in C#
- 7:27Five traps
- 8:26Nine binary search types
- 9:08Type 1 · Find a number in a sorted array
- 15:00Type 2 · Where does it fit?
- 20:54Type 3 · First and last position
- 27:29Type 4 · Smallest number in a rotated array
- 33:39Type 5 · Search in a rotated array
- 39:47Type 6 · Search a sorted grid
- 45:44Type 7 · Find a peak
- 51:51Type 8 · Slowest eating speed
- 58:36Type 9 · Time based key-value store
- 1:05:19Spot the type
- 1:06:05Quiz: which type?
- 1:06:52Recap