Solves
searching
Articles
SRT
Algorithm
Binary search
Finds the “no → yes” boundary in ordered data in log₂ n checks.
O(log n)
2 problems
SRT
Technique
Binary search on the answer
If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving.
O(log D · cost of a check)
2 problems
SRT
Algorithm
Exponential search
Steps 1, 2, 4, 8, … until you overshoot, then binary search: when the bound is unknown or the answer is near.
2⌊log₂ i⌋ + 1 questions to position i
1 problem
DS
Data structure
Binary search tree
Smaller to the left, larger to the right: search, order and the k-th element in the tree's height, from log n to n.
O(h): from O(log n) to O(n)
2 problems
DS
Data structure
AVL tree
A search tree where the branch heights at a node differ by at most 1: height up to ~1.44·log₂ n.
O(log n) for search, insertion and deletion
2 problems
DS
Data structure
B-tree
A tree with hundreds of keys in a page-sized node: a search among a billion keys reads five pages.
O(log n) comparisons, O(log_B n) page reads
2 problems
Problems
Often together
classic 6 interviews 5 binary search 3 search tree 3 tree 3 range queries 3 databases 2 array 1 version control 1 greedy 1 optimization 1 contests 1