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!
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.