Computer Programming

What is binary search ?

Binary search starts by searching of the data in the elements at the mid of the array to determine if the target is in the first or second half of the list. If it is in the first half we do not need to check the second half. If its in the second half we need not check the first half. In other words we estimate half the list from further consideration. We repeat this process until we find the target or determine that it is not in the list.

Binary Search only works for the sorted array. Binary search is a Divide and Conquer technique.




Binary search algorithm:

algorithm binarySearch ()
Return found <Boolean>
first = 0
last = end
loop (first <= last )
   mid = (first + last)/2
   if (target > list [ mid ] )
   LOOK IN UPPER HALF
   first = mid + 1
   else if (target < list [mid])
   LOOK IN LOWER HALF
   last = mid -1
   else
   Found equal : force exit
   first = last + 1
   end if
end loop
locn = mid
if (target equal list mid [mid])
   found = true
   else
   found = false
   end if
   return found
end binarySearch



//TO WRITE A PROGRAM TO SEARCH FOR A GIVEN ELEMENT FROM AN ARRAY USING BINARY SEARCH

//SEARCH TECHNIQUE

#include<iostream.h>
#include<conio.h>


void binsearch(int ar[],int size,int ele)
{       int lb=0,ub=size-1,mid;             //lb=>lower bound,ub=>upper bound

     for(;lb<ub;)
       {
           mid=(lb+ub)/2;

           if(ar[mid]==ele)
             {
                cout<<"\n SEARCH SUCCESSFUL";
                break;
             }

           else
                 if(ar[mid]<ele)
                 ub=mid-1;

           else
               if(ar[mid]>ele)
                  lb=mid+1;
      }

       if(ub<lb)

         cout<<"\n SEARCH UNSUCCESSFUL";

}

void sort(int ar[],int size)               //sorts the array in ascending array using bubble sort
{
     int temp;

     for(int i=0;i<size;i++)
         for(int j=0;j<size-i-1;j++)
          if(ar[j]>ar[j+1])
               {
                temp=ar[j];
                ar[j]=ar[j+1];
                ar[j+1]=temp;

               }

}

void display(int ar[],int size)
{
     for(int i=0;i<size;i++)
         cout<<'\n'<<ar[i];
}

void input(int ar[],int size)
{
     for(int i=0;i<size;i++)
         cin>>ar[i];
}

void main()
{
     clrscr();

     int size;
     cout<<"\n ENTER THE NUMBER OF ELEMENTS REQUIRED IN THE ARRAY :";
     cin>>size;

     int *ar=new int(size);

     cout<<"\n ENTER THE ELEMENTS OF THE ARRAY :\n";

     input(ar,size);         //takes the input from the array

     sort(ar,size);         //sorts the array in the ascending order

     int ele;
     cout<<"\n ENTER THE ELEMENT TO BE FOUND :\n";
     cin>>ele;

     getch();

}