1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include "stdafx.h" #include <iostream> #include <vector> using namespace std; int iterbsearch(vector<int> * data, int target) { int low = 0; int high = data->size() - 1; while (low != high) { int mid = (low + high) / 2; if (data->at(mid) == target) { return mid; } else if (data->at(mid) > target) { high = mid; } else { low = mid + 1; } } if (data->at(low) != target) { return -1; } else { return low; } } int findlowerbound(vector<int> * data, int target) { int low = 0; int high = data->size() - 1; int mid; while (low < high-1) { //cout << low << " " << high << endl; mid = (low + high) / 2; if (data->at(mid) == target) { return target; } else if (data->at(mid) > target) { high = mid; } else { low = mid; } } if (target < data->at(low)) { return -1; } else if (target > data->at(high)) { return data->at(data->size() - 1); } else { return data->at(low); } } int main() { vector<int> v1 = { 1,2,4,5,6,8,9,11,13 }; cout << findlowerbound(&v1,12) << endl; cout << iterbsearch(&v1, 11) << endl; while(1){} return 0; } | cs |