C Program for Binary Search
In this article, we will understand the Binary search algorithm and how to write binary search programs in C. We will see both iterative and recursive approaches and how binary search is able to reduce the time complexity of the search operation as compared to linear search.
What is Binary Search?
Binary Search is an interval searching algorithm used to search for an item in the sorted list. It works by repeatedly dividing the list into two equal parts and then searching for the item that is the part where it can possibly exist.
Unlike linear search, there are a few conditions for applying binary search:
- The list must be sorted.
- Random access to the list member.
It means that we cannot apply the binary search in unsorted or liked data structures.
Algorithm for Binary Search in C
Let be the element we are searching for and the array is sorted in the ascending order.
- Compare with the middle element of the array.
- If matches with the middle element, we return the index of the middle element.
- Else if is greater than the middle element, it means that can only lie in the right half subarray after the middle element. So we repeat steps 1 and 2 for the right half subarray and leave the left half subarray from the algorithm
- Else if is smaller than the middle element, it means that can only lie in the left half subarray before the middle element. So, we repeat steps 1 and 2 for the left half subarray.
- We will keep doing that till we find or there is no element left in the subarray being considered.
As we can see, the binary search ignores the half elements of the subarray after each pass. Due to this, it is able to reduce the time required for searching the element in the array as compared to linear search.
Binary Search Program in C (Recursive)
The following C program implements the binary search algorithm using recursion:
C
// C program to implement binary search using recursion #include <stdio.h> // A recursive binary search function. It returns location // of x in given array arr[l..r] if present, otherwise -1 int binarySearch( int arr[], int l, int r, int x) { // checking if there are elements in the subarray if (r >= l) { // calculating mid point int mid = l + (r - l) / 2; // If the element is present at the middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then it can only // be present in left subarray if (arr[mid] > x) { return binarySearch(arr, l, mid - 1, x); } // Else the element can only be present in right // subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not present in array return -1; } // driver code int main( void ) { // taking a sorted array int arr[] = { 2, 3, 4, 10, 40 }; int size = sizeof (arr) / sizeof (arr[0]); // element to be searched int x = 10; // calling binary search int index = binarySearch(arr, 0, size - 1, x); if (index == -1) { printf ( "Element is not present in array" ); } else { printf ( "Element is present at index %d" , index); } return 0; } |
Output
Element is present at index 3
Complexity Analysis of Binary Search(Recursive)
Time Complexity: O(log n)
Auxiliary Space: O(log n), where n is the number of elements in the array.
Binary Seach Program in C (Iterative)
C
// C Program to implement binary search using iteration #include <stdio.h> // A iterative binary search function. It returns location // of x in given array arr[l..r] if present, otherwise -1 int binarySearch( int arr[], int l, int r, int x) { // the loop will run till there are elements in the // subarray as l > r means that there are no elements to // consider in the given subarray while (l <= r) { // calculating mid point int m = l + (r - l) / 2; // Check if x is present at mid if (arr[m] == x) { return m; } // If x greater than ,, ignore left half if (arr[m] < x) { l = m + 1; } // If x is smaller than m, ignore right half else { r = m - 1; } } // if we reach here, then element was not present return -1; } // driver code int main( void ) { // creating a sorted array int arr[] = { 2, 3, 4, 10, 40 }; int size = sizeof (arr) / sizeof (arr[0]); // element to be searched int x = 24; // calling binary search int result = binarySearch(arr, 0, size - 1, x); if (result == -1) { printf ( "Element is not present in array" ); } else { printf ( "Element is present at index %d" , result); } return 0; } |
Output
Element is not present in array
Complexity Analysis of Binary Search (Iterative)
Time Complexity: O(log n), where n is the number of elements in the array.
Auxiliary Space: O(1)
Please refer complete article on Binary Search for more details!