Understand linear search, binary search intuition, and when to apply each.
Searching means finding a target value in a collection. Linear search checks every element in O(n). Binary search works on sorted data and eliminates half the search space each step, achieving O(log n). Knowing when your data is sorted (or can be sorted) is the first step to applying binary search.
Linear O(n) · Binary O(log n)
O(1) for both iterative approaches
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
scan from left to right, works on any unsorted data, O(n)
requires sorted input, halves search space each step, O(log n)
binary search only works when elements are sorted or monotone
left=0, right=n-1, mid=(left+right)/2, compare and narrow
understand whether to use left <= right or left < right based on problem
binary search on the answer value range, not on array index
sorting costs O(n log n) but enables O(log n) repeated searches