Binary Search

Binary search in C programming

As we have learned linear search takes too long for long size array. So there is another search called binary search.

The objective of binary Search

Search an element item in an array arr[0...n-1] using binary search. If element found then return the position otherwise return -1.

The requirement for binary search

For binary search, it is required that the given array should be sorted in ascending order.

Basic Concept of binary search

In binary search to search an element item, each element is not matched. To perform the binary search the following process is followed...

  1. As we know that an array is a bounded structure that has two boundaries lower bound and upper bound.
  2. Lower bound of the array is 0 and if the array size is represented by n then the upper bound of the array is n-1. so we take two-variable lb and ub and initialized with a lower bound and upper bound respectively. The following code initializes the value of lb and ub.
  3. lb = 0; ub = n - 1;
  4. After initializing lower bound and upper bound we find the mid index by calculating the mid-position by using the following formula.
  5. mid = (lb + ub) / 2;
  6. After finding the mid-position we match the item with the arr[mid], if match found the return the mid otherwise two cases are possible either the item is greater than mid or lower than mid.
  7. If the item is greater than mid we set the lb to mid + 1 and repeat the process again. In this way, we reject the half part array of that is lower than mid position.
  8. If the item is smaller than mid we set the ub to mid - 1 and repeat the process again. In this way, we reject the half part of the array that is higher than mid position.
  9. We repeat this process until lb <= ub because continues we break the array in half. For example, if initially array size is 10 then in the next iteration it will be 5 followed by 2 and 1. When array size is 1 then lb and up becomes the same means this will be the last element to test. if it is also doesn't match then the item not found in the array.
  10. Let's go through the following program to understand the concept.

Program to find an element item in an array using binary search.

#include<stdio.h>
int binary_search(int arr[],int n,int item) {
	int lb = 0; int ub = n - 1;
	int mid;
	
	while(lb <= ub) {
		mid = (lb + ub) / 2;
		
		if(item == arr[mid]) {
			return mid;
		}
		else if(item > arr[mid]) {
			lb = mid + 1;
		}
		else {
			ub = mid - 1;
		}
	}
	return -1;
}
int main() {
	int arr[20];
	int i,n;
	int item,pos;
	
	printf("Enter how many element, (max:20): ");
	scanf("%d",&n);
	
	//Array input
	for(i = 0; i < n; i++) {
		printf("Enter element %d: ",i+1);
		scanf("%d",&arr[i]);
	}
	
	//Item to search
	printf("Enter the item to search: ");
	scanf("%d",&item);
	
	pos = binary_search(arr,n,item);
	
	if(pos != -1) {
		printf("Item found at index %d",pos);
	}else {
		printf("Item not found");
	}
	return 0;
}

Output

Enter how many element, (max:20): 5
Enter element 1: 10
Enter element 2: 20
Enter element 3: 30
Enter element 4: 40
Enter element 5: 50
Enter the item to search: 30
Item found at index 2
Enter how many element, (max:20): 5
Enter element 1: 10
Enter element 2: 20
Enter element 3: 30
Enter element 4: 40
Enter element 5: 50
Enter the item to search: 25
Item not found