本文共 3153 字，大约阅读时间需要 10 分钟。
#include#include #include #include #include #include #include #include #include using namespace std;template vector genArray(){ time_t now_time; now_time = time(NULL); std::default_random_engine generator(now_time); std::uniform_int_distribution distribution(-100,100); auto dice = bind ( distribution, generator ); vector v; for (int &_var: vector (10)) { int e = dice(); v.push_back(e); } sort(v.begin(), v.end()); return v;}/*---------------------------------------------------- * 常规二分查找 *----------------------------------------------------*/int bSearch(vector arr, int size, int value){ size_t mid; size_t low = 0; size_t high = static_cast (size) - 1; while (low <= high) { mid = low + ((high - low) >> 1); if(arr[mid] < value) { low = mid + 1; }else if (arr[mid] > value) { high = mid - 1; }else { return static_cast (mid); } } return -1;}/*---------------------------------------------------- * 二分查找变体一：查找第一个值等于给定值的元素：6 7 7 8 *----------------------------------------------------*/int bSearch_1(vector arr, int size, int value){ size_t mid; size_t low = 0; size_t high = static_cast (size) - 1; while (low <= high) { mid = low + ((high - low) >> 1); if(arr[mid] < value) { low = mid + 1; }else if (arr[mid] > value) { high = mid - 1; }else { if ( (mid==0) || (arr[mid - 1] != value)) return static_cast (mid); else high = mid - 1; } } return -1;}/*---------------------------------------------------- * 二分查找变体二：查找最后一个值等于给定值的元素：6 7 7 8 *----------------------------------------------------*/int bSearch_2(vector arr, int size, int value){ size_t mid; size_t low = 0; size_t high = static_cast (size) - 1; while (low <= high) { mid = low + ((high - low) >> 1); if(arr[mid] < value) { low = mid + 1; }else if (arr[mid] > value) { high = mid - 1; }else { if ( (mid==0) || (arr[mid + 1] != value)) return static_cast (mid); else low = mid + 1; } } return -1;}/*---------------------------------------------------- * 二分查找变体三：查找第一个大于等于给定值的元素：6 7 9 19 查 8 *----------------------------------------------------*/int bSearch_3(vector arr, int size, int value){ size_t mid; size_t low = 0; size_t high = static_cast (size) - 1; while (low <= high) { mid = low + ((high - low) >> 1); if (arr[mid] >= value) { if ( (mid==0) || (arr[mid - 1] < value)) return static_cast (mid); else high = mid - 1; }else { low = mid + 1; } } return -1;}/*---------------------------------------------------- * 二分查找变体四：查找最后一个小于等于给定值的元素：6 7 9 19 查 8 *----------------------------------------------------*/int bSearch_4(vector arr, int size, int value){ size_t mid; size_t low = 0; size_t high = static_cast (size) - 1; size_t len = high; while (low <= high) { mid = low + ((high - low) >> 1); if (arr[mid] <= value) { if ( (mid==len) || (arr[mid + 1] > value)) return static_cast (mid); else low = mid + 1; }else { high = mid - 1; } } return -1;}int main(){ int value; while (1) { vector array = genArray (); copy(array.begin(), array.end(), ostream_iterator (cout, " ")); cout< <<"search value >:"; cin >> value; int pos = bSearch_3(array, static_cast (array.size()), value); cout <<"pos:"< << endl; } return 0;}
转载地址：http://yecii.baihongyu.com/