Binary Search in C. Search algorithms are fundamental in computing, enabling data structures. Binary Search is one of the efficient algorithms for finding an element from a sorted list of items. In this article, we will explain about Binary Search algorithm and write a C program for Binary Search.
Table of Contents
Binary Search
Binary Search is only applicable for sorted data sets. This algorithm divides the search space in half with each iteration, progressively narrowing down the target element position. This method contrasts with linear search strategy where each element is sequentially examined until the target is found or the search space is exhausted.
The Binary Search Algorithm compares the target element with the middle element of the array. if the target value matches with the middle element, The search is successful. Otherwise, if the target is less than the middle element, the search continues in the left subarray, or if the target is greater search continues in the right subarray. This process repeats until the target element is found or the search space becomes zero
C Program for Binary Search
#include <stdio.h>
int binarySearch(int array[], int target, int low, int high)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (array[mid] == target)
{
return mid;
}
if (array[mid] < target)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
void main()
{
int array[] = {21, 34, 45, 56, 76, 78, 87, 89, 90};
int n = sizeof(array) / sizeof(array[0]);
int target = 76;
int result = binarySearch(array, target, 0, n - 1);
if (result == -1)
{
printf("Element not found in the array ");
}
else
{
printf("Element found at index %d", result);
}
}
Output
Complexity of Binary Search
Binary Search time complexity is O(log n) in both average and worst-case scenarios, this shows its ability to manage expensive search operations with minimal steps.
The space complexity of Binary Search remains constant O(1) highlighting its operational economy.
Despite its advantages, the prerequisites or sorted array can be viewed as a limitation, necessitating preliminary sorting that may offset its efficiency gain in certain contexts.
Happy Coding & Learning
1 thought on “Binary Search in C”