DataslopeSearching
Learn linear search, binary search, STL search helpers, common pitfalls, and duplicate-aware variants in C++
Searching means locating a target value in a collection. The right technique depends mainly on whether the data is sorted.
Linear search
Linear search checks each element from left to right until it finds the target or reaches the end. It works on unsorted data and runs in O(n).
Linear search is often right for tiny arrays, one-time scans, linked lists, or unsorted data that is not worth sorting first.
Binary search
Binary search only works on sorted data. It keeps a search interval, checks the middle, and discards half the remaining values each step. That gives O(log n) time.
Use low <= high when both endpoints are inclusive. Compute mid as low + (high - low) / 2 to avoid overflow.
STL search helpers
C++ already includes binary-search algorithms for sorted ranges.
std::binary_searchreturnstrueorfalse.std::lower_boundreturns an iterator to the first element>= target.std::upper_boundreturns an iterator to the first element> target.
Binary search requires sorted data
If the range is not sorted according to the same comparison used by the search, binary search results are meaningless.
Another classic bug is calculating mid as (low + high) / 2. For very large indices, low + high can overflow, so use low + (high - low) / 2.
Variants
When duplicates exist, ordinary binary search may return any matching index. To find the first occurrence, keep searching left after a match.
The insert position is the first index where the target could be placed while keeping the vector sorted. It is exactly what lower_bound computes.
Practice: implement binary search
Implement int binarySearch(const std::vector<int>& v, int target) for a sorted vector. Return the index if found, or -1 if missing.
Practice: first occurrence with duplicates
Implement int firstOccurrence(const std::vector<int>& v, int target). Return the first matching index, or -1 if absent.
Check your understanding
What is the worst-case time complexity of linear search over n elements?
O(n)
O(log n)
O(1)
O(n log n)
What must be true before using binary search on a vector?
The vector must have no duplicates.
The vector must be sorted according to the search comparison.
The vector must contain only positive integers.
The vector must be stored on the heap.
What does std::lower_bound(first, last, x) return?
The first element strictly greater than x.
A boolean indicating whether x exists.
An iterator to the first element not less than x.
The last occurrence of x.
In an inclusive binary search loop, which update is correct after v[mid] < target?
high = mid - 1
low = mid
low = mid + 1
high = mid