Binary search is a divide and conquer strategy to find an element in a sorted list. The binary search is not feasible for unsorted array.Let us consider following array data:

{17,18, 19, 27, 46, 78, 102, 114}
Then how can we find if an element present in the above list? For example to find 19 we would proceed with below steps.

STEP1:
calculate the middle element , in given example 46 is middle element
STEP2:
compare the middle element with the target(19) element
here 19 is less than 46.
STEP3:
if target is equal to the middle element, then return the found index.
STEP4:
if target(19) is less than middle element(46) , then search from index 0 to index (middle -1)
STEP5:
if target is greater than middle element , then search from index (middle +1) to up to last index.

## Complexity analysis of binary search algorithm

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

## Sample c code for binary search algorithm

```#include<stdio.h>
#include<stdlib.h>

int bin_search(int value, int target[], int start, int end) {
if (start > end) {
return -1;
}
int middle = (start + end) / 2;
if (value == target[middle])
return middle;
int v1, v2;
if (value < target[middle]) {
return bin_search(value, target, start, middle - 1);
}
if (value > target[middle]) {
return bin_search(value, target, middle + 1, end);
}

}

int main() {

int arr[] = { 17, 18, 19, 27, 46, 78, 102, 114 };

int end = sizeof(arr) / sizeof(int);

int status = bin_search(19, arr, 0, 7);
if (status == -1)
printf("No match found \n");
else
printf("match found at index %d\n", status);

return 0;
}
```

## Sample c++ code for binary search algorithm

```#include<stdio.h>
#include<iostream>
#include<stdlib.h>

using namespace std;

class binSearch {
private:
int arr[8];
int length;
public:
binSearch(int arrsize);
~binSearch();
int bin_search(int value, int start, int end);
};

binSearch::binSearch(int arrsize) :
arr( { 17, 18, 19, 27, 46, 78, 102, 114 })

{
length = arrsize;
}

binSearch::~binSearch() {

}

int binSearch::bin_search(int value, int start, int end) {
if (start > end) {
return -1;
}
int middle = (start + end) / 2;
if (value == arr[middle])
return middle;
int v1, v2;
if (value < arr[middle]) {
return bin_search(value, start, middle - 1);
}
if (value > arr[middle]) {
return bin_search(value, middle + 1, end);
}

}
int main() {

/*initialize the data*/
binSearch *bins = new binSearch(8);

int a = bins->bin_search(19, 0, 7);
if (a == -1)
cout << "No match found" << endl;
else
cout << "match found at" << a << endl;

return 0;

}
```