Binary Search in C
In this article, we will discuss Binary Search in C Programming. Linear Search and Binary Search are the two popular techniques for searching of elements in a list
Binary Search algorithm is based on the divide and conquer technique which means it will divide the array in two halves, then the searching process takes place.
A binary search algorithm is used to find the position of a specific element in a sorted array. This technique of binary search only works on a sorted array. So an array must be sorted in order to apply binary search.
As the definition of Binary Search is done we are moving towards the working of Binary Search.
In order to understand the working of Binary Search we have to know what does sorted array means?. As we have learn in the definition that in order to apply Binary Search the array should be in Sorted order first.
So Sorted array means element are arranged in ascending order or descending order.
How Binary Search works?
Here we are taking the elements in ascending order.
Let the elements of array are the following.
We have to search whether 85 is present in the array or not. So we will take a variable (Variables are the names you give to computer memory locations which are used to store values in a computer program.) and assign 85 to it i,e. k=85.
In order to find the element Binary Search follows some formula which are
low will be assigned to the 0th index of the array i,e. low=0
High will be assigned to the last index of the array.(high = size of array - 1).
Mid value of the array is calculated by mid=(low+high)/2
So the sorted array that we have taken in figure 1 will transform after following the above rules is depicted below.
Here 0th index is assigned as low (low=0).
High is calculated by size of array -1, so size of array if you calculate there are 7 elements so size will be 7.
Thus high = 7-1 i,e. 6.
mid is calculated by (low + high)/2 i,e. (0+6)/2 which results as 3.
After calculating low, high , mid there are some rules we have to remember.
i) a[mid] < k
here a is the array, K is the required key element that we have to search. mid that we have just calculated.
So a[mid] < k means the key element is greater than the mid value.It gives an idea that our key element is present on the right hand side of the array.
In this case we have to do Low=mid+1 as we have to check the right hand part.
ii) a[mid] > k
It means that key element is less than the mid value so it shows that our key element is on the left hand side part. when this situation arises we have to do High = mid -1.
iii) a[mid]= k
It means the key element is at mid location.
In short we can remener like this
i) a[mid] < k low=mid+1
ii)a[mid] > k high=mid -1
iii)a[mid] = k Element is at mid
Now we are procceding towards finding the key element. Our key element is 85, k=85.
Now the array is divided and we have to check only on the right hand side part.
Let's procced.
As we can see in figure 3
85 > a[mid] i,e. case no. (i) applied here which says if key element is greater than mid do low = mid +1. so low will be now low = mid +1 which is 3 + 1 i,e 4 and high = 6 therefore mid = (low + high)/2 which is (4+6)/2 i,e. 5, we got mid = 5. So our array is tranformed and is shwon in the below figure.
If you see in figure 5 our key value matches with the mid element which we have seen in case iii that says if both are matched then the algorithm will return the index of the element matched. Thus our key element is founded.
As we have learned the working of binary search Lets proced towards the Pseudo Code.
Pesudo Code Of Binary Search
We are moving towards the Algorithm of Binary Search.
Algorithm of Binary Search
Binary Search Program in C
Time Complexity
Now let's see the Time complexity of Binary Search in Best case, worst case, Average case. We will also be learning about space complexity.
Best Case: In Binary Search best case occur when the element is found at its first comparison i,e. when the first mid element itself is the element to be searched. Thus best case time complexsity of Binary Search is O(1).
Average Case: Average Case of Binary Search is O(logn).
Worst Case: Worst Case occurs when we have to keep reducing the search space till only one element has left. Worst Case time complexity of Binary Search is O(logn).
Space Complexity
Advantage of Binary Search
Binary Search is simple and easy to implement, making it a good choice for many application.
It is well suited for searching of larger data sets that are stored in external memory such as hard drive or in the cloud
Binary Search is faster than linear search especially in case of larger arrays
Disadvantage of Binary Search
For Binary Search the array should be sorted.We must first sort it before performing the search
The interaction of Binary Search with memory heiarchy i,e. Caching is poor
It can be less efficient than other algorithm such as hash table for searching of larger dataset that do not fit in memory.
When to use Binary Search
When the data are stored in Contiguous memory
when the dataset is sorted
When the data does not have complex structure.
Conclusion
So far our Binary Search article comes to an end but before ending we just conclude what are the things that we have learned today.
To conclude, it can be said that
Binary Search Algorithm allow us to find element in a sorted list. As Binary Search cannot be performed in case of an unsorted array.
The Time Complexity for Average Case and Worst Case is O(logn).
In order to perform Binary Search Algorithm the array elements should be sorted.
Binary Search is useful for building complex algorithm in Computer Graphics and Machine Learning
Main Banner Image Credit: severalnines.com