Explain about Binary Search with Algorithm

Binary Search:

                    Binary Search technique is implemented on sorted list of elements. It is faster than linear search, hence this method is efficient when the number of elements are large

Algorithm:

                    A non-recursive binary search has three arguments i.e L[ ](address of the list of elements), n(the number of elements in the list), key(the element to be searched).
                   
                    In this search method, the list of element is divided into two groups and the key element is searched in these groups. This process is carriedout until the element is found in the list. If the key element is not found in the list then a message "Unsuccessful search, element not found" is displayed.

Step1:

                    Initialize lowalue = 0, highvalue = 0, L[ ]
                    while(lowvalue <= highvalue) do
                    midvalue = (lowvalue + highvalue)/2
                    goto Step2.
                    Otherwise the condition fails
                    print "Unsuccessful search, element not found"
                    goto Step 5

Step2:
                    check, if(L[midvalue] = key) then
                    print "Element found at midvalue
                    goto Step5.
                    else
                   
Step3:

                    check, if(L[midvalue] > key) then
                    highvalue = midvalue - 1
                    goto step1
                    else

Step4:
         
                    check, if(L[midvalue] < key) then
                    lowvalue = midvalue + 1
                    goto step1

Step5:
                   
                     STOP


Time Complexity:

--> The Time Complexity of binary Search is O(logn / log2).
--> In Worest case O(logn) comparisions are required.
--> The number of comparisions depends on the number of elements in the list.

Program:

#include<stdio.h>
#include<conio.h>
int bs(int[],int,int,int);
void main( )
{
          int a[20],i,n,val,bsf,low,high;
          printf("\nEnter the number of elements: ");
          scanf("%d", &n);
          printf("\nEnter the %d elements: ",n);
          for(i=0;i<n;i++)
          scanf("%d", &a[i]);
          printf("\nEnter the Search element:");
          scanf("%d", &val);
          low=0;
          high=n-1;
          bsf=bs(a,val,low,high);
          if(bsf==-1)
              printf("\nThe element not found");
          else
              printf("The element found at %d location", bsf+1);
}
int bs(int a[], int ele, int low, int high)
{
           int mid;
           while(low<high)
           {
                    mid=(low+high)/2;
                    if(ele==a[mid])
                          return mid;
                    else if(a[mid]>ele)
                          high=mid-1;
                    else if(a[mid]<ele)
                          low=mid+1;
                    else
                          return -1;
             }
}




Thanks for visiting...........