Home

Learning Hub

Articles

Binary Search in C Programming, Explained with Examples.

Imagine you’re searching for a specific book in a library, but you don’t know where it is. Binary Search is like having a librarian who can quickly guide you to the right shelf. It’s a search algorithm used to find an element in a sorted array or a linked list. This powerful tool is one of the most used algorithms for searching data in a collection of elements.

What is a Binary Search?

Binary Search is a sorting algorithm for finding the position of a target value within a sorted array or list. This algorithm repeatedly  divides the search interval in half until the target value is four or the interval is empty. Each step of the binary search algorithm compares the target value with the middle element of the array. If the target is matched with the middle element. Then, It will return the search continuously in the lower half of the array. If the target value is greater, the search will be continuous in the lower half of the array or list. If the target value is greater than the search continuous in the right half. This process is repeated until the desired element is not found or the search interval is empty.

Read also: Sorting in Data Structure

Condition to Apply Binary Search Algorithm in a Data Structure

To apply a Binary Search Algorithm in an array data structure or any data structure. This condition must be applied for using the Binary Search algorithm.

• The data structure must be sorted.
• Access to any element in the data structures takes constant time.

Binary Search Algorithm

In this section, we will see how the Binary Search Algorithm works. 

• First, Divide the Array into two halves 
• Compare the middle element of the search space with the key attribute.
• If the key is found in the middle element. Then, processes will be terminated.
• If the key is not found at the middle element in the array. Choose half will be used as the next search space in the array.
• If the key is smaller than the middle element, the left side is used to search for the target element.
• If the key is larger than the middle element, then the right side is used for the next search element.
• This process is continued until the key is found or the total search space is not available.

How Does Binary Search Algorithm Work?

In this section,  we will see the workings of the binary search algorithm.

Consider an array arr[] = {35,44,98,90,100,102,110}

• Find the mid element in the array. Then, compare it with the element with the key. If the key is less than the mid element, move to the left, and if it is greater than the mid, move the search space to the right. 
• For example, key 110 is greater than the current mid element, for example, 90. The search space moves to the right.
• The key is less than the current mid in 102. The search space moves to the right-hand side.
• If the key matches the value of the mid element, stop the search.

How to Implement a Binary Search Algorithm?

The Binary search algorithm can be implemented in two ways

• Iterative Binary Search Algorithm
• Recursive Binary Search Algorithm

Iterative Binary Search Algorithm

In this section, we will use a Binary Search algorithm in C language using the iterative approach. This method is similar to the recursive method. Let’s dive deep into this method.

The following program demonstrates the  iterative approach in Binary Search Algorithm:

Program

Output

Time Complexity : O(log N)

Auxiliary Space : O(1)

Recursive Binary Search Algorithm

The following program demonstrates the Binary Search Algorithm Recursively.

Program

Output

Time Complexity:

• Best Case : O(1)

• Average Case : O(log N)

• Worst Case : O(log N)

Auxiliary Space: O(1).  If we use call stack in binary search, then auxiliary space will be O(log N).

Application of Binary Search Algorithm

• Searching in Sorting: Binary  Search algorithm commonly used to efficiently search an element in a sorted array. It works by repeatedly dividing the search interval in half. It is very efficient, with a time complexity of O(log n), where n is the number of elements in the arrays.
• Graphics: Binary search algorithms, such as those for ray tracing or texture mapping, are also used in computer graphics.
• Database: It is also used in database searching.

Advantages of Binary Search

There are many advantages to Binary Search algorithms. Let’s dive deep into it one by one.

• The Binary Search algorithm is faster than a linear search algorithm. We can use binary search for large arrays.
• It has less compilation time and thus  better time complexity as compared to other algorithms.

Disadvantages of Binary Search Algorithm

• Binary only works on sorted list or array
• Binary search requires that the data structure must begin the search and be stored in contiguous memory locations.
• Binary search requires that the arrays’  elements be comparable, meaning that they must be able to be ordered. 
• Binary search is not suitable for dynamic data structures like linked lists, where accessing elements by indexing is not efficient.

Conclusion

In this article, we learned about Binary Search in the C programming language. This  powerful algorithm quickly finds elements in sorted arrays. Binary search can drastically improve the performance of search operations compared to linear search algorithms. It is particularly useful in scenarios where the data is stored and needs to be searched repeatedly.