二分法查找,返回有序数组中第一个大于给定值的元素的索引
程序员文章站
2024-03-17 15:22:22
...
//查找有序数组中第一个大于V的索引
int first_upper_bound(int v, vector<int>&nums)
{
if(nums.empty()) return -1;
int n = nums.size()-1;
if(nums[n-1] <= v) return n;
int left = 0,right = nums.size()-1;
while(left < right)
{
int mid = left + (right -left)/2;
if(nums[mid] <= v) left = mid+1;
else right = mid ;
}
return left;
}
int main()
{
vector<int> nums = {1,2,3,4,4,4,5};
int v= 4;
int num = first_upper_bound(v,nums);
std::cout<<num<<std::endl;
}