lower

binary search算法特别讲究细节，微小的改动都会带来不同的结果，这篇博客将放上lower_bound和upper_bound的实现 lower_bound的实现

说明：inputs是升序排序好的数组，target是要搜索的元素

int lower_bound(vector& inputs, int target) { int l = 0, r = inputs.size() - 1; while (l <= r) { int mid = l + (r - l) / 2; // (l + 2)/2 可能会溢出 if (inputs[mid] < target) { // lower_bound和upper_bound的区别！！ l = mid + 1; } else { r = mid - 1; } } return l;}

upper_bound的实现

int upper_bound(vector& inputs, int target) { int l = 0, r = inputs.size() - 1; while (l <= r) { int mid = l + (r - l) / 2; // (l + 2)/2 可能会溢出 if (inputs[mid] <= target) { // lower_bound和upper_bound的区别！！ l = mid + 1; } else { r = mid - 1; } } return l;}