Here you will get program for binary search in C.
Binary search algorithm can be applied on a sorted array to search an element. Search begins with comparing middle element of array to target element. If both are equal then position of element is returned. If target element is less than middle element of array then upper half of array is discarded and again search continued by dividing the lower half. If target element is greater than middle element then lower half is discarded and search is continued in upper half.
Worst Case Time Complexity: O(log n)
Best Case Time Complexity: O(1)
Also Read: Linear Search in C
Program for Binary Search in C
Below program shows the implementation of binary search algorithm in C.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<stdio.h> int main() { int arr[50],i,n,x,flag=0,first,last,mid; printf("Enter size of array:"); scanf("%d",&n); printf("\nEnter array element(ascending order)\n"); for(i=0;i<n;++i) scanf("%d",&arr[i]); printf("\nEnter the element to search:"); scanf("%d",&x); first=0; last=n-1; while(first<=last) { mid=(first+last)/2; if(x==arr[mid]){ flag=1; break; } else if(x>arr[mid]) first=mid+1; else last=mid-1; } if(flag==1) printf("\nElement found at position %d",mid+1); else printf("\nElement not found"); return 0; } |
Output
Enter size of array:6
Enter array element(ascending order)
20 27 40 50 58 99
Enter the element to search:27
Element found at position 2
C program for recursive Binary search
c program for recursive binary search