Searching
Binary search and its many disguises across sorted and rotated structures.
- 1 Lesson
Dry-run engine
Binary Search
A sorted array lets one read at the midpoint discard half of the remaining memory.
- Input
- arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target = 23
- Output · Returns
- Press play to run it
How it works
Read mid = lo + (hi - lo) / 2. If arr[mid] < target, move lo = mid + 1; if it's greater, move hi = mid - 1. Every read halves the window.
sorted_ram_buffer[10]
- lo0
- hi9
- mid4 (val: 16)
- Compare16 < 23
lo=0, hi=9, so mid = 0 + (9 - 0) / 2 = 4, which holds 16. 16 < 23, so the target can only be to the right: discard [0..4] and set lo = 5.
1 / 3
Course Contents
Related courses
- ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems
- StringsCharacter arrays with their own set of classic patterns — two pointers, sliding window, and more.19 lessons · 19 problems
- Linked ListNodes linked one direction by pointers instead of contiguous memory.4 lessons · 12 problems