Visualized DSA Strategies

Episode 8 Binary Search

1 h 9 min · Go

Title card of Episode 8: Binary Search

▶ This video is coming to YouTube soon.

The complete guide to binary search for coding interviews, in Go. First the idea: halve the range with every look, the two templates (an exact value, and where a yes or no question flips), the middle lo + (hi − lo) / 2 (Go's int is 64-bit, but an int32 sum wraps silently, and the standard library writes int(uint(lo+hi) >> 1)), what it saves, sort.Search, sort.SearchInts and slices.BinarySearch, 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, the loop inside sort.Search
  • When lo + hi overflows in Go (int32, 32-bit builds), uint(lo+hi) >> 1, and the safe middle
  • slices.BinarySearch and its (index, found) result, sort.SearchInts, sort.Search, floor and ceiling on a sorted slice
  • 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

  1. 0:00Intro
  2. 0:28Halve the range
  3. 1:04A question that flips once
  4. 1:58Template 1: an exact value
  5. 3:11Template 2: where it flips
  6. 4:13The overflow bug, in Go
  7. 5:37What binary search saves
  8. 6:06sort.Search and slices.BinarySearch
  9. 8:02Five traps
  10. 9:18Nine binary search types
  11. 10:00Type 1 · Find a number in a sorted array
  12. 16:01Type 2 · Where does it fit?
  13. 21:56Type 3 · First and last position
  14. 28:33Type 4 · Smallest number in a rotated array
  15. 34:53Type 5 · Search in a rotated array
  16. 41:05Type 6 · Search a sorted grid
  17. 47:07Type 7 · Find a peak
  18. 53:18Type 8 · Slowest eating speed
  19. 1:00:15Type 9 · Time based key-value store
  20. 1:07:06Spot the type
  21. 1:07:52Quiz: which type?
  22. 1:08:39Recap