A binary search is a simplistic algorithm intended for finding the location of an item stored in a sorted list. There are a few variations to the binary search in C program, such as testing for equality and less-than at each step of the algorithm.
Binary search in C is an example of a simple process that can be used to dissolve 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 algorithm applies to a sorted array for searching an element. The search starts with comparing the target element with the middle element of the array. If value matches then the position of the element is returned.
In case the target element is less than the middle element (considering the array follows an ascending order) of the array then the second half of the array is discarded and the search continues by dividing the first half.
The process is the same when the target element is greater than the middle element, only, in this case, the first half of the array is discarded before continuing with the search. The iteration repeats until a match for the target element is found.
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 int main() { int c, first, last, middle, n, search, array[100]; printf("Enter number of elements:\n"); scanf("%d",&n); printf("Enter %d integers:\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 index %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:
Enter number of elements:
5
Enter 5 integers:
1
9
22
24
46
Enter the value to find:
24
24 is present at index 4.
Other Examples of Implementing a Binary Search in C Program
- Recursive Implementation of Binary Search
NOTE: - This program doesn’t allow you to input the elements as the list is already implemented in it. The program simply demonstrates the way a binary search in C program works!
#include int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); return binarySearch(arr, mid + 1, r, 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); (result == -1) ? printf("The element is not present in array") : printf("The element is present at index %d", result); return 0; }
Output:
The element is present at index 3.
- Iterative Implementation of Binary Search
NOTE: - This program doesn’t allow you to input the elements as the list is already implemented in it. The program simply demonstrates the way a binary search in C program works!
#include int binarySearch(int arr[], int l, int r, int x) { while (l <= r) { int m = l + (r - l) / 2; if (arr[m] == x) return m; if (arr[m] < x) l = m + 1; else r = m - 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); (result == -1) ? printf("The element is not present" " in array") : printf("The element is present at " "index %d", result); return 0; }
Output:
The element is present at index 3.
Recommended Course
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)
Mastering Data Structures & Algorithms using C and C++
Pros and Cons of Binary Search in C
Advantages:
- A fairly simple algorithm based on the divide and conquer approach
- Much faster in comparison to the linear search. Linear search requires N/2 and N comparisons for average and worst-case scenarios. Binary search merely requires a total of log2 (N) and log2 (N) comparisons, respectively for average and worst-case scenarios. To put it simply, linear search on an average requires 500,000 comparisons to be made for a set of million elements. Binary search, on the other hand, requires merely 20 comparisons.
- Often available as an already implemented library routine
Disadvantages:
- Complicated than the linear search
- Great loss in efficiency if the list doesn’t support random-access
- Works only for lists that are sorted and kept sorted
Program Complete!
There is no single authoritative way of implementing a Binary Search in C. Hence, the possibilities are endless. The few examples mentioned in the article are just some of many.
Having an understanding of how binary search works is not only important for gaining adequacy in C but also in other programming languages.
Do you know of any other interesting/effective way of writing a Binary Search in C program? Share with the community via the dedicated comment window below.
People are also Reading:
