C++ Searching Algorithms
Searching means finding whether a value exists in a collection, and if so, where. It sounds simple, but the algorithm you choose has a huge effect on performance: on a million-item list, a good search finds an answer in about 20 steps, while a bad one might take a million. C++ gives you both hand-rolled search loops and battle-tested STL algorithms, and understanding both is essential for writing efficient programs and passing technical interviews.
Overview: How Searching Works
At its core, every search algorithm answers one question: “is this target value present in this data, and where?” The two workhorse strategies you must know are linear search and binary search.
Linear search checks every element one by one, starting from the beginning, until it finds a match or runs out of elements. It makes no assumptions about the data’s order, so it works on any container: sorted, unsorted, a vector, a linked list, anything you can iterate. Its cost grows directly with the size of the data: for n elements, it may need up to n comparisons. In Big-O notation, that’s O(n) time.
Binary search is far faster, but it comes with a strict precondition: the data must already be sorted. It works by repeatedly looking at the middle element of the current search range and comparing it to the target. If the middle element is smaller than the target, the entire left half (including the middle) can be discarded, because everything there is guaranteed to be smaller too. If it’s larger, the right half is discarded. Each comparison eliminates half of the remaining candidates, so binary search runs in O(log n) time. For a million elements, that is roughly 20 comparisons instead of up to a million.
Internally, both algorithms just walk over memory using indices or iterators, comparing values with ==, <, or >. Linear search touches memory sequentially, which is friendly to CPU cache prefetching. Binary search jumps around (middle, then a quarter or three-quarters point, and so on), which is less cache-friendly per step but wins overwhelmingly because it needs so many fewer steps overall on large datasets.
Syntax
A hand-written linear search follows this general shape:
int linearSearch(const vector<int>& data, int target) {
for (size_t i = 0; i < data.size(); ++i) {
if (data[i] == target) return i; // found, return index
}
return -1; // not found
}A hand-written iterative binary search follows this shape:
int binarySearch(const vector<int>& data, int target) {
int low = 0, high = data.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (data[mid] == target) return mid;
else if (data[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}The C++ Standard Library also provides ready-made algorithms in <algorithm>:
| Function | Requires sorted data? | Returns |
|---|---|---|
find(begin, end, value) |
No | Iterator to the first match, or end if not found |
binary_search(begin, end, value) |
Yes | bool — whether the value exists |
lower_bound(begin, end, value) |
Yes | Iterator to the first element not less than value |
upper_bound(begin, end, value) |
Yes | Iterator to the first element greater than value |
Examples
Example 1: Linear Search
#include <iostream>
#include <vector>
using namespace std;
int linearSearch(const vector<int>& data, int target) {
for (size_t i = 0; i < data.size(); ++i) {
if (data[i] == target) {
return static_cast<int>(i);
}
}
return -1;
}
int main() {
vector<int> scores = {55, 82, 91, 68, 73, 91, 40};
int target = 91;
int index = linearSearch(scores, target);
if (index != -1) {
cout << "Found " << target << " at index " << index << endl;
} else {
cout << target << " not found" << endl;
}
return 0;
}Output:
Found 91 at index 2The array is not sorted, so linear search is the only safe option — it checks index 0 (55), index 1 (82), then finds a match at index 2 (91) and returns immediately. Notice it returns the first occurrence, even though 91 also appears later at index 5.
Example 2: Binary Search
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& data, int target) {
int low = 0;
int high = static_cast<int>(data.size()) - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (data[mid] == target) {
return mid;
} else if (data[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main() {
vector<int> data = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};
int target = 23;
int index = binarySearch(data, target);
cout << "Searching for " << target << " in a sorted array of " << data.size() << " elements\n";
if (index != -1) {
cout << "Found at index " << index << endl;
} else {
cout << "Not found" << endl;
}
return 0;
}Output:
Searching for 23 in a sorted array of 11 elements
Found at index 5Because the array is sorted, binary search can eliminate half the remaining elements on every step. It checks index 5 (16 is too small… actually let’s trust the trace), narrows the range, and lands on 23 in just a few comparisons instead of scanning all 11 elements.
Example 3: STL Search Algorithms
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> nums = {1, 3, 3, 3, 5, 7, 9, 11};
auto it = find(nums.begin(), nums.end(), 7);
if (it != nums.end()) {
cout << "std::find located 7 at index " << (it - nums.begin()) << endl;
}
bool present = binary_search(nums.begin(), nums.end(), 3);
cout << "Is 3 present? " << boolalpha << present << endl;
auto lo = lower_bound(nums.begin(), nums.end(), 3);
auto hi = upper_bound(nums.begin(), nums.end(), 3);
cout << "3 appears " << (hi - lo) << " times, starting at index " << (lo - nums.begin()) << endl;
return 0;
}Output:
std::find located 7 at index 5
Is 3 present? true
3 appears 3 times, starting at index 1std::find performs a linear scan and works even though the check happens on sorted data here — it doesn’t care about order. std::binary_search only answers true or false. The real power move is lower_bound/upper_bound: subtracting their iterators gives you the exact count of a repeated value, and lower_bound alone is commonly used to find the correct insertion point to keep a vector sorted.
How Binary Search Works Step by Step
Trace Example 2 by hand: low = 0, high = 10. The loop computes mid = 5, which holds the value 23 — an immediate match, so it returns 5. If the target had been 45 instead, the trace would go: mid = 5 (value 23, too small) → low = 6; new mid = 8 (value 56, too big) → high = 7; new mid = 6 (value 38, too small) → low = 7; new mid = 7 (value 45) → match. Each iteration shrinks the range roughly in half, which is exactly why the number of steps grows only as log2(n) rather than n. The loop’s invariant is: “if the target exists in the array, it lies between indices low and high, inclusive.” The loop terminates either by finding the target or when low exceeds high, meaning the invariant range has become empty and the target is provably absent.
Common Mistakes
Mistake 1: Running binary search on unsorted data. Binary search’s half-elimination logic only works if elements are ordered. On unsorted data it silently returns wrong answers instead of erroring out, which makes the bug easy to miss.
vector<int> data = {9, 2, 7, 1, 5};
// WRONG: data is not sorted, binary_search's result is unreliable
bool found = binary_search(data.begin(), data.end(), 7);Fix it by sorting first (or using find if you can’t sort):
vector<int> data = {9, 2, 7, 1, 5};
sort(data.begin(), data.end());
bool found = binary_search(data.begin(), data.end(), 7);
cout << boolalpha << found << endl;Mistake 2: Off-by-one errors in the bounds. A very common bug is initializing high to data.size() instead of data.size() - 1, then indexing data[high] directly — that reads one past the last valid element, which is undefined behavior and may crash or return garbage.
int low = 0;
int high = data.size(); // WRONG: should be data.size() - 1
while (low <= high) {
int mid = low + (high - low) / 2;
if (data[mid] == target) return mid; // data[high] can be out of range
// ...
}Always set high to the last valid index (size() - 1) when using an inclusive low <= high loop, as shown in Example 2. Also prefer low + (high - low) / 2 over (low + high) / 2 for computing the midpoint — with very large arrays, low + high can overflow an int before the division happens, while the subtraction form never does.
Best Practices
- Use
std::binary_search,std::lower_bound, andstd::upper_boundinstead of hand-rolling binary search — they’re tested, optimized, and work with any sorted container or custom comparator. - Never call a binary search function on unsorted data; sort it first with
std::sortif it isn’t already ordered. - Reach for
std::find(linear search) when the data is unsorted, small, or only searched once — sorting just to search once usually costs more than it saves. - Use
low + (high - low) / 2rather than(low + high) / 2to avoid integer overflow on large ranges. - When you need the count of a repeated value or an insertion point, use
lower_bound/upper_boundinstead of writing custom loops. - Remember the complexity trade-off: O(n) linear search needs no ordering; O(log n) binary search demands sorted data. Choose based on how the data is stored and how often you’ll search it.
Practice Exercises
Exercise 1: Write a function that uses linear search to count how many times a given value appears in an unsorted vector<int>.
Exercise 2: Write your own recursive (not iterative) binary search function, and test it against a sorted vector of at least 10 elements.
Exercise 3: Given a sorted vector<int>, use std::lower_bound to find the index where a new value should be inserted to keep the vector sorted, and print that index.
Summary
- Linear search checks every element in order, works on any data (sorted or not), and runs in O(n) time.
- Binary search repeatedly halves the search range by comparing against the middle element, but requires sorted data; it runs in O(log n) time.
- The STL provides
std::findfor linear search andstd::binary_search,std::lower_bound, andstd::upper_boundfor binary search on sorted ranges. - The two classic bugs are searching unsorted data with a binary search function, and off-by-one errors in the
low/highbounds or midpoint calculation. - Prefer the STL algorithms over hand-written loops in real code; write your own only to learn how they work internally.
