Home Arrays Binary Search

Binary Search

by nikoo28
0 comment

Let us consider the problem of searching a word in a dictionary, in general we directly go to some approximate page [say, middle page] start searching from that point. If the name that we are searching is same then we are done with the search. If the page is before the selected page then we apply the same process for the first half otherwise apply the same process to the second half. Binary search also works the same way. The algorithm applying such a strategy is referred to as binary search algorithm.

Iterative version:-

//iterative binary search which returns index of element
int binarySearchIterative(int arr[], int size, int data)
{
	int low = 0;
	int high = size-1;
	int mid;
	
	while(low<=high)
	{
		mid = low + (high-low)/2; //To avoid overflow by (low + high)
		
		if(arr[mid] == data)
			return mid;
		else
		{
			if(arr[mid] < data)
				low = mid + 1; // search in right half
			else
				high = mid - 1; // search in left half
		}
	}
	
	return -1;
}

Recursive version:-

//recursive binary search which returns index of element
int binarySearchRecursive(int arr[], int low, int high, int data)
{
	if(low<=high)
	{
		int mid = low + (high-low)/2; // To avoid overflow
	
		if(arr[mid] == data)
			return mid;
		else
		{
			if(arr[mid] < data)
				//search in right half.
				return binarySearchRecursive(arr, mid+1, high, data);
			else
				//search in left half.
				return binarySearchRecursive(arr, low, mid-1, data);
		}
	}
	return -1;
}
0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More