Binary Search

What is Binary Search?

Before learning what binary search is let us have a look at the definition of searching.

Searching is a process of finding a given element in the list. The process is successful if the element is present in the list, and hence the process returns the location of that particular element. On the otherside, if we do not find the given element in the list then the search is called unsuccessful.

The two popular searching techniques are Linear Search and Binary Search. Here let us discuss the Binary Search Algorithm.

Binary search algorithm is the search technique that works efficiently for the lists that are in a sorted order. Hence, in order to search for an element in a list using the binary search technique, we must first ensure that we have a sorted list.

We have already seen that the binary search algorithm follows the divide and conquer approach. Here, we divide the list into two halves, and the element that we search is compared with the middle element of the list. If the match is found then, the search is successful and the location of the middle element is returned. Else, we search for the element in either of the halves of the list depending upon the result produced by the match.

Here is the algorithm for Binary search:

1. BinarySearch(a, lowerbound, upperbound, val) //where ‘a’ is the given array, ‘lowerbound’ is the index of the first array element, ‘upperbound’ is the index of the last array element, and ‘val’ is the value to be searched. 
2. Step 1: set begin = lowerbound, end = upperbound, position = – 1  
3. Step 2: repeat steps 3 and 4 while begin <=end  
4. Step 3: set mid = (begin + end)/2  
5. Step 4: if a[mid] = val  
6. set position = mid  
7. print position  
8. go to step 6  
9. else if a[mid] > val  
10. set end = mid – 1  
11. else  
12. set begin = mid + 1  
13. [end of if]  
14. [end of loop]  
15. Step 5: if position = -1  
16. print “element not found”  
17. [end of if]  
18. Step 6: exit  

How does the algorithm work?

First, let us consider a sorted array to understand the working of the Binary search algorithm. There are two way in which we can implement the binary search algorithm –

• Iterative method
• Recursive method

Among the two methods, the recursive method of binary search follows the divide and conquer approach.

Complexity of Binary Search

Now, let’s see the time and space complexity of Binary search in the best case, average case, and worst case.

1. Best Case Time Complexity – The best case in binary search occurs when the element to be searched is found in first comparison, i.e., when the first middle element of the list is the element to be searched. The best-case time complexity of Binary search would be O(1).

2. Average Case Time Complexity – The time complexity for the average case of Binary search is O(logn).

3. Worst Case Time Complexity – The worst case of binary search occurs when we have to keep reducing the search space till it has only one element. Which means that we find the element in the last comparison. The time complexity for this case of Binary search is O(long).

4. Space Compexity – The space complexity for binary sriracha would be O(n).

Program for the implementation of Binary Search

#include <stdio.h>  
int binarySearch(int a[], int begin, int end, int value) {    
int mid;     
if(end >= begin) {        
mid = (begin + end)/2;    

•  /* if the element to be searched is present at the middle of the list */  

1. 1.         if(a[mid] == value) {                 
   2.             return mid+1;    
   3.         }    

• /* if the element to be searched is less than the middle element, then it can only be in left subarray */  

1. 1.         else if(a[mid] < value) {  
   2.             return binarySearch(a, mid+1, end, value);    
   3.         }    

• /* if the element to be searched is more than the middle element, then it can only be in right subarray */  

1.         else {  
2.             return binarySearch(a, begin, mid-1, value);    
3.         }          
4.     }    
5.     return -1;     
6. }   
7.   int main() {  
8.   int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // array given to us  
9.   int value = 40; // value to be searched  
10.   int n = sizeof(a) / sizeof(a[0]); // size of array  
11.   int result = binarySearch(a, 0, n-1, value); // Storing the result  
12.   printf(“The array elements are – \n”);  
13.   for (int k = 0; k < n; k++) {
14.   printf(“%d “, a[i]); 
15. }  
16.   printf(“Element to be searched – %d\n”, value);  
17.   if (result == -1)  
18.   printf(“Element is not present in the array\n”);  
19.   else  
20.   printf(“Element found at position – %d\n”, result);  
21.   return 0;  
22. }