## Binary Search

### 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)
{
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;
}
}```

### 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

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