Performance and Time Complexity
For any algorithm based on comparison, its worst-case time cannot be lower than O(log2n), so binary search is the optimal algorithm in the worst case.
Found Not found
Best O(1) O(log2n)
Averag O(log2n) O(log2n)
Worst O(log2n) O(log2n)
In general there are two implementations:
Recursive Binary Search
int BinarySearch(int A[], int i, int, j, int x) { int m = -1; // if not found, then return -1 if (i <= j) { m = (i + j) / 2; if (A[m] < x) m = BinarySearch(A, m + 1, j, x); else if (x < A[m]) m = BinarySearch(A, i, m - 1, x); } return m; }
Iterative Binary Search
int BinarySearch2(int A[], int n, int x) { int i = 0, j = n - 1, m = 0; while (i <= j) { m = (i + j) / 2; if (x < A[m]) j = m - 1; else if (A[m] < x) i = m + 1; else return m; } return -1; //not found }
Binary Search in C++ STL
std::binary_search returns true if val in the range [first, last), else returns false. For example, we need to check 6 exists in array a:
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { vector<int> a = { 1, 2, 3, 4, 5, 6, 7, 8 }; int val = 6; if (binary_search(arr.begin(), arr.end(), val)) cout << "found " << endl; else cout << "not found" << endl; return 0; }
std::lower_bound returns an iterator pointing to the first element in the range [first, last) that is greater or equal to val, or last if no such element is found.
std::upper_bound returns an iterator pointing to the first element in the range [first, last) that is greater than val, or last if no such element is found.
For example, we check if 4 exists:
int main() { vector<int> a = { 1, 2, 2, 4, 4, 4, 5, 5 }; const auto it = std::lower_bound(a.begin(), a.end(), 4); if (it != a.end()) cout << "found 4 at position " << ( it - v.begin() ) << endl; else cout << "not found" << endl; return 0; }
Leave a Reply