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;

}

 



Related Contents to follow