DSA sheet · Binary Search
Binary Search DSA Notebook
My study notes from the Binary Search playlist. Each page is written so that a beginner (or me, after forgetting everything) can read it once and understand the intuition, why each condition moves low or high, the Python code line by line, and a full dry run with the search range drawn shrinking.
The one idea behind every page
If you can ask a yes/no question whose answers line up like
That halving turns n steps into about log₂ n steps: about 20 checks for a million items.
no no no yes yes yes (or the other way round), you can find the switch point by checking the middle and throwing away half each time.That halving turns n steps into about log₂ n steps: about 20 checks for a million items.
Every page follows the same order:
① question in simple words → ② constraints → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ line by line → ⑧ dry run → ⑨ complexity & remember
Start here
Classic search on a sorted array
Rotated arrays & peaks
- 5Search in Rotated Sorted Arraysorted half
- 6Minimum in Rotated Sorted Arraysorted half
- 7Find Peak Elementslope
- 9Rotate Array by K (+ find K)reversal · BS bonus
Lower bound & upper bound
- 8First & Last Positionlower · upper bound
- 10Count Occurrenceslast − first + 1
- 11Floor & Ceilingclosest values
Matrices
- 12Search a Sorted Matrixstaircase
- 13Search a 2D Matrix IIO(n + m)
- 22Kth Smallest in Sorted Matrixsearch on answer
Binary search on the answer: minimise the value
- 14Koko Eating Bananasbrute → BS on answer
- 15Ship Packages Within D Daysbrute → BS on answer
- 16Minimum Speed to Arrive on TimeBS on answer
- 18Minimum Days for m BouquetsBS on answer
- 20Allocate Minimum Pagesmin of max
- 21Split Array Largest Summin of max
Binary search on the answer: maximise the gap
Numbers are the order in the playlist. "Next →" at the top of each page follows that order. Trees and BSTs are in the separate Binary Tree and BST notebooks.