Binary Search in C++

Level 5295 keystrokes

On a sorted vector, binary_search tells whether a value is present, and lower_bound finds the first element not less than a value. Both run in O(log n).

C++ code

// Binary search requires sorted data
1vector<int> nums = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
2
// boolalpha prints bool values as true/false instead of 1/0
3cout << boolalpha;
// 7 is in the vector: prints true
4cout << binary_search(nums.begin(), nums.end(), 7) << endl;
// 8 is not: prints false
5cout << binary_search(nums.begin(), nums.end(), 8) << endl;
6
// Iterator to the first element >= 10
7auto it = lower_bound(nums.begin(), nums.end(), 10);
// Prints 11 (if no such element existed, it would be end() and must not be dereferenced)
8cout << "Lower bound of 10: " << *it << endl;

Output

true
false
Lower bound of 10: 11
Practice typing this code

Practice typing this code. Results are not recorded in the rankings.

Symbols in this code

The symbols you type in this C++ code and how often they appear.

  • <× 17
  • ,× 15
  • (× 9
  • )× 9
  • ;× 6
  • .× 6
  • _× 3
  • "× 2
  • =× 2
  • :× 1

More C++ examples at level 5

← C++ typing practice