最左边那个 17 在哪
数组是 13、15、17、17、17、23、24。运行下面这段程序:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int left_bound(const vector<int>& a, int target) {
// 最左边那个 target 的下标,没有返回 -1
int lo = 0, hi = (int)a.size() - 1, got = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) {
got = mid;
hi = mid - 1;
} else if (a[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return got;
}
int main() {
vector<int> A = {13, 15, 17, 17, 17, 23, 24};
cout << left_bound(A, 17) << endl;
}
(本题用 g++ -std=c++17 -O0 编译。)