Visualized DSA Strategies

Episode 8 Binary Search

1 h 9 min · JavaScript

Title card of Episode 8: Binary Search

▶ This video is coming to YouTube soon.

The complete guide to binary search for coding interviews, in JavaScript. 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 with Math.floor and why the bit shift (lo + hi) >> 1 wraps once the sum passes 2³¹, what it saves, why JavaScript has no binary search of its own (indexOf and findIndex scan) and the lowerBound you write instead, 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 can't overflow a JavaScript number, why (lo + hi) >> 1 wraps past 2³¹, and the safe middle with Math.floor
  • No built-in binary search: indexOf and findIndex scan in O(n), so write lowerBound for insertion points, counts, 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

  1. 0:00Intro
  2. 0:29Halve the range
  3. 1:04A question that flips once
  4. 1:59Template 1: an exact value
  5. 3:13Template 2: where it flips
  6. 4:06The middle: where >> breaks
  7. 5:43What binary search saves
  8. 6:13Binary search in JavaScript: write lowerBound
  9. 7:58Five traps
  10. 8:59Nine binary search types
  11. 9:41Type 1 · Find a number in a sorted array
  12. 15:29Type 2 · Where does it fit?
  13. 21:27Type 3 · First and last position
  14. 28:06Type 4 · Smallest number in a rotated array
  15. 34:36Type 5 · Search in a rotated array
  16. 41:07Type 6 · Search a sorted grid
  17. 47:12Type 7 · Find a peak
  18. 53:23Type 8 · Slowest eating speed
  19. 1:00:13Type 9 · Time based key-value store
  20. 1:07:10Spot the type
  21. 1:07:55Quiz: which type?
  22. 1:08:43Recap