Binary search is a time-tested algorithm designed to locate a specific element within a sorted list. Unlike linear search, which inspects each element in sequence, binary search cuts the list in half with each comparison, quickly narrowing the possibilities until the desired value is found or until the search space is exhausted.
Here’s how it works: the algorithm begins by examining the middle element of the list. If that element matches the target, the search is over. If the target is smaller, the algorithm focuses only on the left half of the list. If it’s larger, it shifts its attention to the right half. This process repeats, each time halving the remaining list, until the item is found or the section under consideration becomes empty.
The catch is that binary search only works on data that is already sorted. Without a predictable order, the algorithm’s divide-and-conquer strategy breaks down. But when that condition is met, binary search offers exceptional speed and efficiency. For a list of one million elements, it can find a match in about 20 steps thanks to its logarithmic time complexity, O(log n).
Binary search in C is an example of a simple process that can be used to solve complex problems. As such, it is an important foundational concept that you will find in almost all the good books on the C programming language.
Before giving you the code for establishing a binary search in C, let’s first understand how exactly the algorithm works.
How Does it Work?
Binary search is an algorithm built for speed, but only when the data plays by the rules. It works exclusively on sorted arrays and begins by comparing the target value to the element at the center of the list. If the middle element is a match, the job is done and the position is returned.
But if the target is smaller than the middle element, assuming the list is sorted in ascending order, the algorithm dismisses the entire right half of the array and continues the search on the left. If the target is larger, it flips the script, discarding the left half instead. This halving continues with each step, zeroing in on the target until it’s either located or confirmed absent.
It's a process defined by precision and efficiency, making binary search a go-to solution whenever speed and order matter.
Binary Search in C Program
The following code implements binary search in C programming language. Although it can only be used for sorted arrays, it is fast in comparison to the linear search.
If the requirements ask for using binary search on an unsorted array, then it needs to be sorted first before using the binary search algorithm on it. For doing so, you can make use of some sorting technique, such as the bubble sort or the merge sort.
NOTE: - The code mentioned below assumes that the input numbers follow an ascending order!
Here goes the code for Binary Search in C:
#include <stdio.h>
int main() {
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements:\n");
scanf("%d", &n);
printf("Enter %d integers (in sorted order):\n", n);
for (c = 0; c < n; c++) {
scanf("%d", &array[c]);
}
printf("Enter the value to find:\n");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first + last) / 2;
while (first <= last) {
if (array[middle] < search) {
first = middle + 1;
} else if (array[middle] == search) {
printf("%d is present at position %d.\n", search, middle + 1);
break;
} else {
last = middle - 1;
}
middle = (first + last) / 2;
}
if (first > last) {
printf("Not found! %d is not present in the list.\n", search);
}
return 0;
}Sample Output:
Sample Output:
Enter number of elements:
5
Enter 5 integers (in sorted order):
1
9
22
24
46
Enter the value to find:
24
24 is present at position 4.Other Examples of Implementing a Binary Search in C Program
- Recursive Implementation of Binary Search
NOTE: This program uses a predefined, sorted list and does not accept user input. It simply demonstrates how recursive binary search works in C.
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int x) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, left, mid - 1, x);
return binarySearch(arr, mid + 1, right, x);
}
return -1;
}
int main(void) {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
printf("The element is not present in the array.\n");
else
printf("The element is present at index %d.\n", result);
return 0;
}Here's the output.
The element is present at index 3.
Iterative Implementation of Binary Search
NOTE: This program also uses a predefined, sorted list and does not accept user input. It demonstrates how to implement binary search iteratively.
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int x) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main(void) {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
printf("The element is not present in the array.\n");
else
printf("The element is present at index %d.\n", result);
return 0;
}Here's the output:
The element is present at index 3.Time Complexities of the Binary Search Algorithm
Suppose T(N) is the time complexity of the binary search for a set of N elements. Then,
T(N) = T(N/2) + O(1) (By means of the recurrence relation) - (i)
Now, applying Masters Theorem for computing run time complexity of recurrence relations i.e.
T(N) = aT(N/b) + f(N) - (ii)
Comparing equation (ii) with (i), we get,
a = 1, b = 2
Hence, log (a base b) = 1 = c - (iii)
Now, f(N) = n^c log^k(n) //k = 0 - (iv)
Using (iii) and (iv) in equation (ii), we get,
T(N) = O(N^c log^(k+1)N) = O(log(N)) - (v)
This is the worst-case time complexity for binary search. Now, the best case in which the only comparison is made. Therefore, N = 1. So, we get,
O(log(1)) = O(1) (as log(1) = 1)
Therefore, time complexities for Binary Search in different cases are:
Best Case
O(1)
Worst Case
O(log n)
Pros and Cons of Binary Search in C
Binary search remains one of the most powerful and enduring techniques in the programmer’s toolkit, particularly for those working in C. At its core, binary search is a straightforward algorithm built on the classic divide-and-conquer strategy. When applied correctly, it offers a dramatic improvement in efficiency compared to more naive approaches like linear search.
The appeal of binary search lies in its speed. While a linear search might require up to half a million comparisons to locate a value in a list of one million elements, binary search can do the same job in about 20 steps. That’s because linear search progresses element by element, whereas binary search cuts the list in half with each pass, reducing the number of necessary comparisons to approximately log₂(N) in both average and worst-case scenarios.
For many developers, it’s a relief to know that this efficient method is often built into standard libraries, allowing them to leverage it without writing the implementation from scratch.
But this speed does come with caveats. Binary search is not as universally applicable as it might seem. It only works on lists that are sorted and kept sorted. In cases where the data is unordered, developers must first sort the list, which can introduce significant overhead. The algorithm also assumes random access to elements, meaning it performs poorly on data structures like linked lists where such access is inefficient.
For beginners, binary search can feel more complex than linear alternatives, particularly when considering edge cases and recursion.
There’s no single authoritative way to implement binary search in C, and that’s part of its charm. The examples provided earlier in this article are just a few of the many valid approaches. Whether written iteratively or recursively, tailored for user input or static arrays, each version highlights different strengths and trade-offs.
Understanding binary search isn’t just essential for mastering C. It’s foundational for becoming proficient in programming more broadly. Its logic appears in countless contexts, from search engines to database indexing. For aspiring developers, knowing how and when to apply binary search is as much about learning how to think algorithmically as it is about writing efficient code.
Have a unique twist on the binary search algorithm in C? Join the discussion and share your method with the community below.
