All lessons
LESSON 35/53Searching and Sorting
Binary Search
GOALSearch a sorted array by halving it each time.
Looking a word up in a dictionary, you do not start at page one — you open the middle and decide which half to keep. Binary search is exactly that. One condition: the data must already be SORTED.
ON THIS PAGE
SHOW EXAMPLE IN
//THE EXAMPLE
main.cpp
#include <iostream>
#include <vector>
using namespace std;
int bsearch(const vector<int>& v, int target) {
int lo = 0, hi = (int)v.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (v[mid] == target) return mid;
if (v[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int main() {
vector<int> v = {4, 8, 15, 16, 23, 42};
cout << bsearch(v, 23) << endl;
cout << bsearch(v, 5) << endl;
return 0;
}> what you see
4 -1
//LINE BY LINE
Watch it run
The whole array is still in play: lo = 0, hi = 5.
The three places it goes wrong
Binary search is short but it has three places to get wrong. When it misbehaves, check these first.
| Mistake | What happens |
|---|---|
hi = v.size() | Массиваас хэтэрнэ / reads past the end |
while (lo < hi) | Сүүлийн элементийг алдана / misses the last element |
lo = mid | Хэзээ ч дуусахгүй / loops forever |
The quickest test: run it by hand on an array of one element, then two. All three mistakes show up there.
The ones already written for you
In a contest you rarely write it yourself — the standard library has it. You still have to know what it does.
// first position where v[i] >= x
int i = lower_bound(v.begin(), v.end(), x) - v.begin();
// is x present at all?
bool here = binary_search(v.begin(), v.end(), x);Both assume the data is SORTED. On unsorted data they do not complain — they just answer wrongly.