Binary Search in C

Binary Search in C
Satyam Chaudhary
Data Structure May 27, 2023

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.

Fig 1: Example of an array

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.

Fig 2: Illustration of variables low,mid,high

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.

Fig 3: Searching of element 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.

Fig 4: key element is equal to mid

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

Fig 5: Output when element is founded
Fig 5: Output when element is not found

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.

Fig 8: Time Comlpexity of Binary Search

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

Fig 9: Space Comlpexity of Binary Search

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

searching methods
searching algorithms in data structure
binary search in c
binary search in data structure
binary search algorithm
binary search pseudo code
binary search time complexity
binary search program
code output

Satyam Chaudhary


Satyam is a brilliant Engineering Undergraduate and proud Indian. He is passoinate towards web development and acquiring new skills.

He help students in understanding the concepts with a correct approach and solve their academic problems.

We are here to clear your doubts with an easy step by step approach.