Program For Binary Search[How to]

                                    Binary Search

   Goal--How to do Binary Search In a Given Array?

   Method Used-- Divide and Conquer

    Explanation:

                              Binary Search is best Example of Divide and Conquer Technique.In this first we divide the Problem into Sub problem such that  solution to that sub problem is solution for our real problem.

As we all know that **Binary search is always performed on sorted array.**

Steps:

1.Calculate middle element of Given Array. 

 2. Compare middle element with given number. Then there will be three Cases:                           

           2.1 Given number is equal to middle element  then return it as

           result.

           2.2 If Given number is less than middle  element,then replace

          given array with left half of the given array. Go to step1.

           2.3 If Middle element is greater than given element then replace

           the given array with right half of the given array.  Go to step 1.

3. Perform Above steps Until you finds the given element otherwise return False.

Program:

This Program is in c++, but if you are clear with concept you can implement in any language.

#include <iostream>

#include<conio.h>

using namespace std;

int main()

       {

            int a[30],num,p[30];

            int end,mid,i,k,beg;

            beg=0;

            cout<<"How many elements you want to have in array\n";

            cin>>k;

            cout<<"Enter Elements of Array:\n";

            for(i=0;i<k;i++)

             {

                             cin>>a[i];

                             p[i]=i;

             }

            cout<<"Enter element to be search\n"; 

            cin>>num;

            /*First we sort the enter bcoz Binary search is always performed on sorted list..*/

           for(i=0;i<k;i++)

              {

                int j;

                for(j=0;j<k;j++)

                   {

                      if(a[i]<a[j])

                        {

                           int temp=a[i];

                            a[i]=a[j];

                            a[j]=temp;

                            temp=p[i];

                            p[i]=p[j];

                            p[j]=temp;

                        }   

                   }  

                }    

             end=k-1;

            mid=int((end+beg)/2); //because our index start from 0(beg).

            while(beg<=end & a[mid]!=num)           

              {

                      

                        if(num<a[mid])

                           {

                                  end=mid-1;

            

                           }

                        else

                           {

                              beg=mid+1;

                           } 

                           mid=int((beg+end)/2) ;

              } 

              

           if(a[mid]==num)   

               cout<<"Element Matched at index"<<p[mid]<<"\t[where first element at 0 index]";

           else

              cout<<"Element is not in List\n";

             getch();

   }    

Output:

 

 

Complexity:

Complexity is measured by number of comaparisons.So here we divide array in half after each comparison.So we can write

                                           2^f(n)>n

                    after  taking log on both side(with Base 2)-

                                      f(n)log2=logn

                                       f(n)=logn.

Limitations:

There are 2 requirements  of Binary search :

1.Array must be sorted.

2.One must have direct access to its middle element in any sublist.

In this situation,we will use linked list or Binary Search tree for store Data.

                                                           

                       

     

If you want to share more information about topic discussed above or find anything incorrect Please do comments.