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.
Get curriculum highlights, career paths, industry insights and accelerate your technology journey.
Download brochure
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
#include <stdio.h>
// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high – low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x is greater, ignore the left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore the right half
else
high = mid – 1;
}
// If we reach here, then the element was not present
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 343, 888, 1025, 1053, 1984 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 1984;
int result = binarySearch(arr, 0, n – 1, x);
(result == -1) ? printf(“Element is not present”
” in array”)
: printf(“Element is present at “
“index %d”,
result);
return 0;
}
Output
Element is present at index 4
Time Complexity : O(log N)
Auxiliary Space : O(1)
Recursive Binary Search Algorithm
The following program demonstrates the Binary Search Algorithm Recursively.
Program
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high – low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, low, mid – 1, x);
return binarySearch(arr, mid + 1, high, x);
}
return -1;
}
// Driver code
int main()
{
int arr[] = { 93, 343, 599, 790, 1015 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 1015;
int result = binarySearch(arr, 0, n – 1, x);
(result == -1)
? printf(“Element is not present in array”)
: printf(“Element is present at index %d”, result);
return 0;
}
Output
Element is present at index 4
Complexity Analysis of Binary Search
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.
FAQs
When should I use Binary Search in C language?
Binary search is the best algorithm when you have a sorted list or array. It is very useful when you need to find an element in large datasets where the linear searching algorithm would be slow.
Is binary search always faster than linear search?
Binary search is faster than linear search only when the data is sorted. If the data is not sorted, a linear search is often more appropriate.
Are there any limitations to Binary Search in C language?
The Binary Search algorithm requires sorted data. If the sorted data is not provided, another search algorithm will be helpful.
Can binary search be applied to non-numeric data?
Yes, the Binary search algorithm can also be applied to non-numeric data, as there is a defined order for the elements. For example, it can also be used to search for strings in alphabetical order.
Can Binary search be implemented recursively?
Yes, we can implement the binary search algorithm both iteratively and recursively. The recursive approach uses the external space in the memory stack.
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
