Subscribe:

Labels

Sunday, February 14, 2010

Binary search

#include<iostream.h>

class bsearch
{
public:
 int a[10];
 void input();
 void binarySearch(int lb, int ub, int key);
};
void bsearch::input()
{
 int i;
 cout<<"Input should be sorted numbers \n";
 for(i=0;i<10;i++)
 {
  cin>>a[i];
 }
}
void bsearch::binarySearch(int lb, int ub, int key)
{
 int mid;
    int comparisonCount = 1;   
    
    mid = (lb + ub)/2;
 
 while((a[mid] != key) && (lb <= ub))
    {
  comparisonCount++;
        if (a[mid] > key) 
        {
   ub = mid - 1;   
        }                                                     
        else                                               
        {
   lb = mid + 1;    
        }
        mid = (lb + ub)/2;
 }
    if(lb <= ub)
    {
  cout<< "The number was found in a subscript: "<<mid <<"\n";
  cout<< a[mid];
        cout<< "\n The binary search found the number after " << comparisonCount << " comparisons.\n";             
    }
 else
  cout<< "Sorry, the number is not in this array list. The binary search made "<<comparisonCount << "comparisons.";
    return; 
}
void main()
{
 int key;

 bsearch b;

 b.input();
 cout<< "Enter the key or element to search \n";
 cin>>key;

 b.binarySearch(0, 9, key); 
}

No comments:

Post a Comment