// 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; }
http://www.waitingfy.com/?p=464
原文链接: https://www.cnblogs.com/javawebsoa/archive/2013/04/03/2998084.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/83146
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!