Friday, March 23, 2012

Binary Search Integer Array C Code Algorithm (Simplified code to learn)

What are search algorithms?
Given a database, the first thing you would want to do is probably search through its entries to see if a particular entry exists. This is why search algorithms are one of the most basic and widely used algorithms, and one of the first algorithms taught in any class.

Binary Search drastically reduces the worst-case time required to search through a database. However, it can be used only when the database is sorted i.e. when the entries are arranged either in ascending or descending order.

Following binary search algorithm(in C language) takes user inputs to load the specified data structure array in this case and then sorts it using insertion sort approach, you could also use other sorting methods. Then it print the sorted array of integers. It asks for user to input what entry you want to search, it then prints if particular entry if found or not.
Yes, we can add even more functionality to this code, but I made it simple enough so that other people can understand it and go further to add more towards it.
(Please leave your feedback) Code is:

#include<stdio.h>
//this function sorts the array using insertion sort
int sort(int array[],int n)
{
   int i,j,temp;
   for(i=1;i<n;i++)
   {
          temp=array[i];
          j=i-1;
          while(temp<array[j] && j>=0)
          {
                  array[j+1]=array[j];
                  j=j-1;
          }
          array[j+1]=temp;
   }
}

//this function gets data from user to load into data array
int get_data(int array[],int n)
{
   int i;
   printf("Enter data for array :\n");
   for(i=0;i<n;i++)
   {
          scanf("%d",&array[i]);
   }
}

//this function prints the sorted array
int out_data(int array[],int n)
{
   int i;
   printf("Array after sorting......\n\n");
   for(i=0;i<n;i++)
   {
          printf("%d ",array[i]);
   }
}

//this function searches for particular number entry in the data array
int binary_search(int a[], int low, int high, int target)
{
    if (high < low)
        return -1;
    int middle = (low + high)/2;
    if (target < a[middle])
        return bi_search(a, low, middle-1, target);
    else if (target > a[middle])
        return bi_search(a, middle+1, high, target);
    else if (target == a[middle])
        return middle;
}

//its main code which loads user inputs to functions and perform binary search after sorting the data array
main()
{
//make sure array size is hard coded in this program (30) therefore enter number of array elements less than 30
   int n,array[30],k,b;
   printf("\n\nEnter number of elements you want to enter to data(less than 30 since array size is 30):");
   scanf("%d",&n);
   get_data(array,n);
   sort(array,n);
   out_data(array,n);
   printf("\n\nEnter value to search :");
   scanf("%d",&b);
   k=binary_search(array,0,n-1,b);
   if(k==-1)
   printf("-->%d is not found......!\n",b);
   else
   printf("-->%d is found......!\n\n",b);
}
}




0 comments:

Post a Comment