Wednesday, 2 October 2013

Binary search

 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.


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

  1. #include<stdio.h>
  2. int binarySearch(int* arr,int low,int high,int num){
  3.     int mid;
  4.     //termination case if not found
  5.     if(low>high)
  6.         return -1;
  7.     mid=((low+high)/2);
  8.     //termination case if found
  9.     if(arr[mid]==num)
  10.         return mid;
  11.     //Selecting SubArray recursivily search
  12.     if(arr[mid]<num){
  13.                 return binarySearch(arr,mid+1,high,num);
  14.         }
  15.         else{
  16.             return binarySearch(arr,low,mid-1,num);
  17.         }
  18. }
  19. main(){
  20.         int num;
  21.         int arr[]={32,34,43,54,56,58,66,87,96,100,103,104,1010};
  22.        
  23.         scanf("Enter Number To Search : %d",&num);
  24.         printf("index of %d is %d \n",num,binarySearch(arr,0,(sizeof(arr)/sizeof(int))-1,num));
  25. }

If You Found Any bug Please Suggest
Thank U

1 comment:

  1. wow.. thanks bro what a great blog I like it.. thanks for ur content..
    be_A_hacker

    ReplyDelete

THANKS FOR UR GREAT COMMENT

Blogger Widgets