Spread the love

C program for binary search

Binary search is generally employed on sorted array. Suppose you have sorted array and you want to search for a single element in array then a simple approach is to scan whole array to find particular element like this

// Simple approach
// If x is present then return its location,  otherwise return -1
int search(int arr[], int n, int x)
{
    int i;
    for (i=0; i<n; i++)
        if (arr[i] == x)
         return i;
    return -1;
}

 

The time complexity of above algorithm is O(n) because we scan whole array, as the number of element increase in array our searching time would also increase.

Algorithm

BinarySearchAlgorithm

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n). We basically ignore half of the elements just after one comparison.
1) Compare element to search with the middle element.
2) If element matches with middle element, we return the mid index.
3) Else If element is greater than the mid element, then element can only lie in right half sub array after the mid element. So we recur for right half.
4) Else (element is smaller) recur for the left half.

C program for binary search

#include<stdlib.h>
#include<stdio.h>
 
/* Driver Functions */
int BinarySearch_Iterative(int A[], int size, int element);
int BinarySearch_FirstOccurrence(int A[], int size, int element);
int BinarySearch_Recursive(int A[], int start, int end, int element);
 
/* Main Method */
int main()
{
	int A[] = {0,12,6,12,12,18,34,45,55,99};
	
	printf(" BinarySearch_Iterative() 55 at Index = %d \n",BinarySearch_Iterative(A,10,55));
	printf(" BinarySearch_Recursive() 17 at Index = %d \n",BinarySearch_Recursive(A,0,9,34));
	printf(" BinarySearch_FirstOccurrence() 12's first occurrence at Index = %d \n",BinarySearch_FirstOccurrence(A,9,12));
	
	return 0;
}
 
/* Iterative method */
int BinarySearch_Iterative(int A[], int size, int element)
{
	int start = 0;
	int end = size-1;
	while(start<=end)
	{
		int mid = (start+end)/2;
		
		if( A[mid] ==  element)	return mid; 		// Check if element is present at mid
		
		else if( element < A[mid] )	end = mid-1;	// If element greater, ignore left half
		
		else start = mid+1;							// If element is smaller, ignore right half
	}
	return -1;										// if we reach here, then element was not present
}
 
/* Recursive method */
int BinarySearch_Recursive(int A[], int start, int end, int element)
{
	if(start>end) return -1;					// if start become greater than end, then element was not present
	
	int mid = (start+end)/2;					// Calculating mid at every recursive call
	
	if( A[mid] == element )	return mid;			// Check if element is present at mid
	
	else if( element < A[mid] )	
		BinarySearch_Recursive(A, start, mid-1, element);	// If element greater, ignore left half
	
	else 
		BinarySearch_Recursive(A, mid+1, end, element);		// If element is smaller, ignore right half
}

/* Binary search to find first or last occurrence of element */
int BinarySearch_FirstOccurrence(int A[], int size, int element)
{
	int result;
	int start = 0;
	int end = size-1;
	while(start<=end)
	{
		int mid = (start+end)/2;
		if( A[mid] ==  element)			// Check if element is present at mid
		{
			result = mid; 	
			end = mid - 1;				// Change this statement "start = mid + 1", for last occurrence
		}
		else if( element < A[mid] )	
			end = mid-1;				// If element greater, ignore left half
		
		else 
			start = mid+1;				// If element is smaller, ignore right half
	}
	return result;						// if we reach here, then return element's occurrence index
}

 

Suggested Reading