Binary Search 二分查找,二分搜索 C++

print?// BSearch.cpp : Defines the entry point for the console application.  
//  
 
#include "stdafx.h"  
#include <iostream>  
 
using namespace std; 
 
template <class T> 
void PrintfNum(T a[],const int& n); 
 
 
 
/**
* search n in a[], return the index, if not find, return -1.
*/ 
template <class T> 
int BSearch(T a[],const int& length,const int& n){ 
    int left = 0, right = length - 1; 
    while(left <= right){ 
        int middle = (left + right) / 2; 
 
        //cout << "middle:" <<middle << " ,left:" << left << " ,right:" << right << endl;  
        if(n < a[middle]){ 
            right = middle - 1; 
        }else if(n > a[middle]){ 
            left = middle + 1; 
        }else{ 
            return middle; 
        } 
    } 
    return -1; 
} 
/**
* A better one
* search n in a[], return the index, if not find, return -1.
*/ 
template <class T> 
int BetterBSearch(T a[],const int& length,const int& n){ 
   
    int left = -1, right = length - 1; 
    while(left+1 != right){  //left < right && a[left] < n <= a[right]  
        int middle = (left + right) / 2; 
        if(a[middle] < n){      //a[left] < n  
            left = middle; 
        }else{                  //a[right] >= n  
            right = middle; 
        } 
    } 
    if(right >= length || a[right] != n )//no find  
        return - 1; 
    return right; 
} 
 
 
 
/**
* Test function
*/ 
bool TestBSearch(){ 
    const int NUM = 20; 
    int BeginNum = 10; 
    int t[NUM]; 
    for(int i = 0; i< NUM; ++i){ 
        t[i] = BeginNum; 
        ++BeginNum; 
    } 
    bool result = true; 
    for(int j = 0 ;j < NUM; ++j){ 
        if(BSearch(t, NUM , t[j]) != j){ 
            result = false; 
        } 
    } 
    // test no find  
    if(BSearch(t,NUM,t[0] - 1) != -1 || BSearch(t,NUM,t[NUM-1] + 1) != -1){ 
        result = false; 
    } 
    return result; 
} 
 
/**
* Test function
*/ 
bool TestBetterBSearch(){ 
    const int NUM = 20; 
    int BeginNum = 10; 
    int t[NUM]; 
    for(int i = 0; i< NUM; ++i){ 
        t[i] = BeginNum; 
        ++BeginNum; 
    } 
    bool result = true; 
    for(int j = 0 ;j < NUM; ++j){ 
        if(BetterBSearch(t, NUM , t[j]) != j){ 
            result = false; 
        } 
    } 
    // test no find  
    if(BetterBSearch(t,NUM,t[0] - 1) != -1 || BetterBSearch(t,NUM,t[NUM-1] + 1) != -1){ 
        result = false; 
    } 
    return result; 
} 
 
int main(int argc, char* argv[]) 
{ 
    const int NUM = 10; 
    int t[NUM] = {10,11,12,13,14,15,16,17,18,20}; 
 
    PrintfNum(t,NUM); 
 
    for(int i = 0 ;i < NUM; ++i){ 
       cout << t[i] << " was at index: " << BSearch(t, NUM , t[i]) << endl;  
    } 
    cout << "searching 100 in array t, result: "<< BSearch(t, NUM , 100) << endl; 
     
    cout << endl; 
    cout << "BSearch test result:" << TestBSearch() << endl; 
 
    cout << "BetterBSearch test result:" << TestBetterBSearch() << endl; 
    return 0; 
} 
 
template <class T> 
void PrintfNum(T a[],const int& n){ 
    for(int i = 0; i < n; ++i){ 
        cout << a[i] << ","; 
    } 
    cout << endl; 
} 

// BSearch.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

template <class T>
void PrintfNum(T a[],const int& n);

/**
* search n in a[], return the index, if not find, return -1.
*/
template <class T>
int BSearch(T a[],const int& length,const int& n){
 int left = 0, right = length - 1;
 while(left <= right){
  int middle = (left + right) / 2;

  //cout << "middle:" <<middle << " ,left:" << left << " ,right:" << right << endl;
  if(n < a[middle]){
   right = middle - 1;
  }else if(n > a[middle]){
   left = middle + 1;
  }else{
   return middle;
  }
 }
 return -1;
}
/**
* A better one
* search n in a[], return the index, if not find, return -1.
*/
template <class T>
int BetterBSearch(T a[],const int& length,const int& n){
 
 int left = -1, right = length - 1;
 while(left+1 != right){  //left < right && a[left] < n <= a[right]
  int middle = (left + right) / 2;
  if(a[middle] < n){      //a[left] < n
   left = middle;
  }else{                  //a[right] >= n
   right = middle;
  }
 }
 if(right >= length || a[right] != n )//no find
  return - 1;
 return right;
}

/**
* Test function
*/
bool TestBSearch(){
 const int NUM = 20;
 int BeginNum = 10;
 int t[NUM];
 for(int i = 0; i< NUM; ++i){
  t[i] = BeginNum;
  ++BeginNum;
 }
 bool result = true;
    for(int j = 0 ;j < NUM; ++j){
  if(BSearch(t, NUM , t[j]) != j){
   result = false;
  }
 }
 // test no find
 if(BSearch(t,NUM,t[0] - 1) != -1 || BSearch(t,NUM,t[NUM-1] + 1) != -1){
  result = false;
 }
 return result;
}

/**
* Test function
*/
bool TestBetterBSearch(){
 const int NUM = 20;
 int BeginNum = 10;
 int t[NUM];
 for(int i = 0; i< NUM; ++i){
  t[i] = BeginNum;
  ++BeginNum;
 }
 bool result = true;
    for(int j = 0 ;j < NUM; ++j){
  if(BetterBSearch(t, NUM , t[j]) != j){
   result = false;
  }
 }
 // test no find
 if(BetterBSearch(t,NUM,t[0] - 1) != -1 || BetterBSearch(t,NUM,t[NUM-1] + 1) != -1){
  result = false;
 }
 return result;
}

int main(int argc, char* argv[])
{
 const int NUM = 10;
 int t[NUM] = {10,11,12,13,14,15,16,17,18,20};

 PrintfNum(t,NUM);

 for(int i = 0 ;i < NUM; ++i){
       cout << t[i] << " was at index: " << BSearch(t, NUM , t[i]) << endl;
 }
 cout << "searching 100 in array t, result: "<< BSearch(t, NUM , 100) << endl;
 
 cout << endl;
 cout << "BSearch test result:" << TestBSearch() << endl;

 cout << "BetterBSearch test result:" << TestBetterBSearch() << endl;
 return 0;
}

template <class T>
void PrintfNum(T a[],const int& n){
 for(int i = 0; i < n; ++i){
  cout << a[i] << ",";
 }
 cout << endl;
}