Advertisement
tsnaik

Sequential, binary search (iterative and recursive way)

Oct 22nd, 2014
410
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.85 KB | None | 0 0
  1. #include<stdio.h>
  2.  
  3. int seq_search(int [], int, int);
  4. int bin_search(int [], int, int);
  5. int rbin_search(int [],int, int, int);
  6.  
  7. void main()
  8. {
  9. //  int arr[]={5,100};
  10. //  int arr[]={5};
  11. //  int arr[]={5,7,9,30,31,39};
  12. //  int arr[]={2,2,5,5,5,5,7,7,7,9,9,9,9,9};
  13. //  int arr[]={100};
  14. //  int arr[]={};
  15.     int arr[]={-5,-3,0,5,39};
  16.     int i,key,size;
  17.  
  18.     size=sizeof(arr)/sizeof(int);
  19. //  printf("%d",size);
  20.  
  21. //sequential search
  22.  
  23.     printf("Using Sequential Search: ");
  24.    
  25.     if((i=(seq_search(arr,key=5,size)))!=-1)
  26.     {
  27.         printf("\nFound %d at position %d", key, i);
  28.     }
  29.     else
  30.     {
  31.         printf("\n%d was not found",key);
  32.     }
  33.  
  34.         if((i=(seq_search(arr,key=-3,size)))!=-1)
  35.         {
  36.                 printf("\nFound %d at position %d", key, i);
  37.         }
  38.         else
  39.         {
  40.                 printf("\n%d was not found",key);
  41.         }
  42.  
  43.         if((i=(seq_search(arr,key=39,size)))!=-1)
  44.         {
  45.                 printf("\nFound %d at position %d", key, i);
  46.         }
  47.         else
  48.         {
  49.                 printf("\n%d was not found",key);
  50.         }
  51.  
  52.      if((i=(seq_search(arr,key=100,size)))!=-1)
  53.         {
  54.                 printf("\nFound %d at position %d", key, i);
  55.         }
  56.         else
  57.         {
  58.                 printf("\n%d was not found",key);
  59.         }
  60.  
  61. //Non recursive binary search
  62.  
  63.     printf("\n\n\nUsing Binary Search(Non-recursive): ");
  64.    
  65.     if((i=(bin_search(arr,key=5,size)))!=-1)
  66.     {
  67.         printf("\nFound %d at position %d", key, i);
  68.     }
  69.     else
  70.     {
  71.         printf("\n%d was not found",key);
  72.     }
  73.  
  74.         if((i=(bin_search(arr,key=-3,size)))!=-1)
  75.         {
  76.                 printf("\nFound %d at position %d", key, i);
  77.         }
  78.         else
  79.         {
  80.                 printf("\n%d was not found",key);
  81.         }
  82.  
  83.         if((i=(bin_search(arr,key=39,size)))!=-1)
  84.         {
  85.                 printf("\nFound %d at position %d", key, i);
  86.         }
  87.         else
  88.         {
  89.                 printf("\n%d was not found",key);
  90.         }
  91.  
  92.      if((i=(bin_search(arr,key=100,size)))!=-1)
  93.         {
  94.                 printf("\nFound %d at position %d", key, i);
  95.         }
  96.         else
  97.         {
  98.                 printf("\n%d was not found",key);
  99.         }
  100.  
  101. //recursive binary search
  102.  
  103.     printf("\n\n\nUsing Binary Search(recursive): ");
  104.    
  105.     if((i=(rbin_search(arr,key=5,0,size-1)))!=-1)
  106.     {
  107.         printf("\nFound %d at position %d", key, i);
  108.     }
  109.     else
  110.     {
  111.         printf("\n%d was not found",key);
  112.     }
  113.  
  114.         if((i=(rbin_search(arr,key=-3,0,size-1)))!=-1)
  115.         {
  116.                 printf("\nFound %d at position %d", key, i);
  117.         }
  118.         else
  119.         {
  120.                 printf("\n%d was not found",key);
  121.         }
  122.  
  123.         if((i=(rbin_search(arr,key=39,0,size-1)))!=-1)
  124.         {
  125.                 printf("\nFound %d at position %d", key, i);
  126.         }
  127.         else
  128.         {
  129.                 printf("\n%d was not found",key);
  130.         }
  131.  
  132.      if((i=(rbin_search(arr,key=100,0,size-1)))!=-1)
  133.         {
  134.                 printf("\nFound %d at position %d", key, i);
  135.         }
  136.         else
  137.         {
  138.                 printf("\n%d was not found",key);
  139.         }
  140.  
  141.     printf("\n");
  142. }
  143.  
  144. int seq_search(int arr[], int key, int size)
  145. {
  146.     int i;
  147.    
  148.     for(i=0;i<size;i++)
  149.     {
  150.         if(arr[i]==key)
  151.         {
  152.             return i;
  153.         }
  154.     }
  155.     return -1; //not found
  156. }
  157.  
  158. int bin_search(int arr[], int key, int size)
  159. {
  160.     int low=0, high=size-1,mid;
  161.    
  162.     while(high>=low)
  163.     {
  164.         mid=(high+low)/2;
  165.  
  166.         if(arr[mid]==key)
  167.         {
  168.             return mid;
  169.         }
  170.         else if(key<arr[mid])
  171.         {
  172.             high=mid-1;
  173.         }
  174.         else
  175.         {
  176.             low=mid+1;
  177.         }
  178.     }
  179.     return -1; //not found 
  180. }
  181.  
  182. int rbin_search(int arr[], int key, int low, int high)
  183. {
  184.     int mid;
  185.    
  186.     if(high<low)
  187.     {
  188.         return -1; //not found
  189.     }
  190.    
  191.     mid=(high+low)/2;
  192.  
  193.     if(arr[mid]==key)
  194.     {
  195.         return mid;
  196.     }
  197.     else if(key<arr[mid])
  198.     {
  199.         return (rbin_search(arr, key, low, mid-1));
  200.     }
  201.     else
  202.     {
  203.         return (rbin_search(arr, key, mid+1, high));
  204.     }
  205. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement