博客

//2.3-5 采用递归方式的二分查找,注意输入的数组是有顺序的
#include <iostream>
#include <vector>
using namespace std;


vector<int>::size_type Binary_Search(vector<int> A,int key,vector<int>::size_type first,vector<int>::size_type last)
{
        if(first>last)
              return -1;
         vector<int>::size_type mid;
         mid=(first+last)/2;
         if(key==A[mid])
               return mid;
         else
              if(key>A[mid])
                   return Binary_Search(A,key,mid+1,last);
             else
                  return Binary_Search(A,key,first,mid-1);
}


int main()
{
       vector<int> A;
       int x,key;
       cout<<"input the number you want to search:";
       cin>>key;
       cout<<"Please input some numbers:";
       while(cin>>x)
            A.push_back(x);
        vector<int>::size_type i;
        i=Binary_Search(A,key,0,A.size());
        if(i>=0)
            cout<<"We find the number "<<key<<" and it's location is "<<i<<endl;
        else
            cout<<"There is no "<<key<<" in the vector A."<<endl;
}
*/
//采用非递归方式
#include <iostream>
#include <vector>
using namespace std;


vector<int>::size_type Binary_Search(vector<int> A,int key,vector<int>::size_type first,vector<int>::size_type last)
{
         while(first<=last)
        {
              vector<int>::size_type mid;
              mid=(first+last)/2;
              if(key==A[mid])
                   return mid;
              else
                   if(key>A[mid])
                        first=mid+1;
                   else
                        last=mid-1;
        }
         return -1;
}


int main()
{
      vector<int> A;
      int x,key;
      cout<<"input the number you want to search:";
      cin>>key;
      cout<<"Please input some numbers:";
      while(cin>>x)
          A.push_back(x);
       vector<int>::size_type i;
       i=Binary_Search(A,key,0,A.size());
       if(i>=0)
            cout<<"We find the number "<<key<<" and it's location is "<<i<<endl;
       else
            cout<<"There is no "<<key<<" in the vector A."<<endl;
}