Before going to the program first let us understand what is a Binary Search?
Binary Search:
Binary search is a searching technique used to quickly search the element from the given sorted array list. If the element to be searched is found then its position is printed.
To finding the element from the unsorted array using Binary Search,
- First Sort the given unsorted array using some sorting technique like selection sort, quick sort, etc.
- Then use the Binary Search algorithm to find the given element from the array list.
Program code for Binary Search:
#include<stdio.h>
#include<conio.h>
void main()
{ int a[10],i,n,item,flag=0,low,high,mid; clrscr(); printf("n Enter the size of an array: "); scanf("%d",&n); printf("n Enter the elements in ascending order: "); for(i=0;i<n;i++) { scanf("%d",&a[i]); } printf("n Enter the number to be search: "); scanf("%d",&item); low=0,high=n-1; while(low<=high) { mid=(low+high)/2; if(item==a[mid]) { flag=1; break; } else if(item<a[mid]) { high=mid-1; } else low=mid+1; } if(flag==0) printf("n The number is not found"); else printf("n The number is found and its position is: %d",mid+1); getch();
}
Step by Step working of the above Program Code:
- First the computer reads the array in ascending order from the user.
- Then it read the element to be searched.
- Then it sets the value of low = 0 and high = n-1.
- Then using while loop the value of low is compared with high.
- if it is less than or equal to, then the value of mid is assigned as follows:
- mid=(low+high)/2
- if search element = a[mid],then the value of flag is set to 1.
- elseif the search element < a[mid], then mid-1 is assigned to high.
- else mid+1 is assigned to low.
- if it is less than or equal to, then the value of mid is assigned as follows:
- Finally if flag = 0 , then it is printed as “the number is not found” else it is printed as “the element is in the list and its position is (position)”.
Output:
