Sorting algorithms and binary search variations — fundamental to efficient problem solving.
Time
Binary Search: O(log n), Merge Sort: O(n log n)
Space
Merge Sort: O(n), Quick Sort: O(log n)
Problems
4 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Binary Search | Easy | Google Amazon Microsoft |
| 2 | Search in Rotated Sorted Array | Medium | Google Amazon Meta |
| 3 | Kth Largest Element (Quick Select) | Medium | Google Meta Amazon |
| 4 | Median of Two Sorted Arrays | Hard | Google Amazon Microsoft |
Binary search works on any monotonic function, not just sorted arrays
"Binary search on answer": when you can't search the array directly but can verify if a value works
Merge Sort is stable, Quick Sort is not
For Top K problems: use a min-heap of size K for O(n log k)
