THis method is very fast & efficient. this method require element in list be in sorted order.
In this metod we compare it with element present at the center of list.IF it matches then search is successful . Otherwise the list is divided into two halves.
One from 0th element to center element (first half).
Another from center element to last element(Second half).
AS a result all element in first haf is smaller than center element,All element of second half are larger than cenetr element.
If key(elemnt to be search) is smaller than center element. above procedure repeat in first half. Otherwise in second half.
In this metod we compare it with element present at the center of list.IF it matches then search is successful . Otherwise the list is divided into two halves.
One from 0th element to center element (first half).
Another from center element to last element(Second half).
AS a result all element in first haf is smaller than center element,All element of second half are larger than cenetr element.
If key(elemnt to be search) is smaller than center element. above procedure repeat in first half. Otherwise in second half.
C code::
Basic Approach
// BINARY search ::
// only applicable for sorted list
#include<stdio.h>
#include<stdlib.h>
main()
{
int up=9,lower=0,mid,num,i;
int ar[10]={12,34,46,53,67,145,264,345,957,3455};
printf("\n element in list are :: \n\n");
for(i=0;i<=9;i++)
{
printf(" %d ",ar[i]);
}
printf("\n\n\t Enter number you wan't to search ::");
scanf("%d",&num);
for(mid=((lower+up)/2);lower<=up ; mid=((lower+up)/2)) // condition for for loop
{
if(num==ar[mid])
{
printf("\n\n\n\t\t position of given element is :: %d",mid+1);
exit(0);
}
else
{
if(num>ar[mid])
{
lower=mid+1;
}
else
up=mid-1;
}
}
printf("\n\n\n inserted no not found in this list");
}
OUTPUT ::Recursive Approach for Binary Search
- #include<stdio.h>
- int binarySearch(int* arr,int low,int high,int num){
- int mid;
- //termination case if not found
- if(low>high)
- return -1;
- mid=((low+high)/2);
- //termination case if found
- if(arr[mid]==num)
- return mid;
- //Selecting SubArray recursivily search
- if(arr[mid]<num){
- return binarySearch(arr,mid+1,high,num);
- }
- else{
- return binarySearch(arr,low,mid-1,num);
- }
- }
- main(){
- int num;
- int arr[]={32,34,43,54,56,58,66,87,96,100,103,104,1010};
- scanf("Enter Number To Search : %d",&num);
- printf("index of %d is %d \n",num,binarySearch(arr,0,(sizeof(arr)/sizeof(int))-1,num));
- }
If You Found Any bug Please Suggest
Thank U
wow.. thanks bro what a great blog I like it.. thanks for ur content..
ReplyDeletebe_A_hacker