# Binary Search Algorithm C++

## Binary Search Algorithm C++

Binary search algorithm in C++ relies on a divide and conquer strategy to find a value within an already-sorted collection. Binary search locates the position of an item in a sorted array. Binary search compare an input search key to the middle element of the array and the comparison determines whether the element equals the input, less than the input or greater. The return value is the element position in the array.

### Bibary Search Algorithm complexity

• Worst case performance O(log n)
• Best case performance O(1)
• Average case performance O(log n)
• Worst case space complexity O(1)

### Binary Search Algorithm Arrays implementation

```#include <cstdlib>
#include <iostream>
using namespace std;

int binary_search(int array[],int first,int last, int value);

int main() {

int list;

for (int k=0; k<11; k++)
list[k]=2*k+1;

cout<< "binary search results: "<< binary_search(list,1,21,11)<<endl;

return 0;
}//end of main
int binary_search(int array[],int first,int last, int search_key)
{
int index;

if (first > last)
index = -1;

else
{
int mid = (first + last)/2;

if (search_key == array[mid])
index = mid;
else

if (search_key < array[mid])
index = binary_search(array,first, mid-1, search_key);
else
index = binary_search(array, mid+1, last, search_key);

} // end if
return index;
}// end binarySearch

```

## program output

```My array contains: 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40
binary search found value 26 at position: 13

```