Binary Search

TUTORIAL

1. Binary Search Implementations And Common Errors

Binary Search Implementations And Common Errors

We suggest you do not use library functions for binary search as its very likely that you will be explicitly asked to implement the binary search in interviews.

Implementation of Binary Search

// binary search example in C/C++
/* here Arr is an of integer type, n is size of array 
   and target is element to be found */

int binarySearch(int *Arr, int n, int target) {

	//set stating and ending index
	int start = 0, ending = n-1;

	while(start <= ending) {
		// take mid of the list
		int mid = (start + end) / 2;

		// we found a match
		if(Arr[mid] == target) {
			return mid; 
		}
		// go on right side
		else if(Arr[mid] < target) {
			start = mid + 1;
		}
		// go on left side
		else {
			end = mid - 1;
		}
	}
	// element is not present in list
	return -1;
}

// binary search example in Java
/* here Arr is an of integer type, n is size of array 
   and target is element to be found */

int binarySearch(int Arr[], int n, int target) {

	//set stating and ending index
	int start = 0, ending = n-1;

	while(start <= ending) {
		// take mid of the list
		int mid = (start + end) / 2;

		// we found a match
		if(Arr[mid] == target) {
			return mid; 
		}
		// go on right side
		else if(Arr[mid] < target) {
			start = mid + 1;
		}
		// go on left side
		else {
			end = mid - 1;
		}
	}
	// element is not present in list
	return -1;
}

# binary search example in Python
# here Arr is an of integer type, n is size of array 
#	and target is element to be found
def binarySearch(Arr, n, target) :
	#set stating and ending index
	start, end = 0, n-1

	while start <= end :
		mid = (start + end) / 2
		# we found a match
		if Arr[mid] == target :
			return mid
		# go on right side
		elif Arr[mid] < target :
			start = mid + 1
		# go on left side
		else :
			end = mid - 1;
	# element is not present in list
	return -1

Walkthrough Examples :

COUNTELEMENTS ROTATEDARRAY