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

补充：软件开发 , C++ ,