Binary Search

Searching Algorithm

Share

About

In this search technique we divide the given array into two halves at each level and look for the key element in one of the two halves. This algorithm works only for sorted array. It is similar to searching a word in a dictionary. We roughly start from the middle, and if we are look for a word starting with say E then we discard the other half and look in the first half and repeat the process till we get the result.

  • It works only for sorted array.
  • At each level the array is halved and the key is searched in any one of the half while the other half is rejected.
  • Best case occurs when the key we are looking for is present in the middle of the array.
  • Worst case occurs when the key is not present.

Pseudo Code


/*a[0:n-1] is an array of n elements. key is the element being searched.
*/
BinarySearch(a, n, key)
Begin
    Set start = 0, end = n-1, mid = (start + end)/2;
    while( start <= end && a[mid] != key) do
        if (key < a[mid]) then
            Set end = mid – 1;		//search in the left half
        else
            Set start = mid + 1;		//search in the right half
        endif
        Set mid = (start + end)/2;
    endwhile
    if(start > end)
        return -1;        //key not found
    return mid;        //returning key index
End

Order of Binary Search

If there are n elements in the array. Then in each level the array is halved and the search is reduced to one half of the array.
Therefore, if there are n elements then it will require floor(log2n+1) iterations.
So, we can write order as O(log2n).

Binary search code in C


#include 

//function declaration
int binarySearch(int *a, int n, int key);

int main(){
	//variable declaration
	int arr[10], i, key;
	
	//input
	printf("Enter elements of the array: ");
	for(i = 0; i < 10; i++)
		scanf("%d", &arr[i]);
	printf("Enter key: ");
	scanf("%d", &key);
	
	//search
	i = binarySearch(arr, 10, key);
	
	//output
	if(i == -1)
		printf("Key not found.\n");
	else
		printf("Key at index: %d\n", i);
		
	return 0;
}

//function definition
int binarySearch(int *a, int n, int key){
	int start = 0, end = n - 1, mid = (start + end) / 2;
	while(start <= end && a[mid] != key){
		if(key < a[mid])
			end = mid - 1;
		else
			start = mid + 1;
		mid = (start + end) / 2;
	}
	if(start > end)
		return -1;	//key not found
	return mid;
}

Recently Added