题目描述（牛客例题） 请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
示例1
输入
5,4,[1,2,4,4,5]输出
3解法一：
class Solution {
public:
/**
* 二分查找
* @param n int整型 数组长度
* @param v int整型 查找值
* @param a int整型vector 有序数组
* @return int整型
*/
int upper_bound_(int n, int v, vector& a) {
// write code here
//数组为空时返回值
if(n==0)
return 1;
//定义区间左值、中值和右值
int left=0,right=n-1;
int index;
//当left和right重合时进行最后一次比较
while(left<=right){
index=(left+right)/2;
if(a[index]>=v){//查找值小于等于中值时
if(index==0||a[index-1] 【算法分析与设计|算法系列——二分查找（例题）】解法二：
class Solution {
public:
/**
* 二分查找
* @param n int整型 数组长度
* @param v int整型 查找值
* @param a int整型vector 有序数组
* @return int整型
*/
int upper_bound_(int n, int v, vector& a) {
// write code here
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (a[mid] < v) {
left = mid + 1;
} else if (a[mid] > v) {
right = mid - 1;
} else if (a[mid] == v) {
// 别返回，锁定左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= n || a[left] < v)
return n+1;
return left+1;
}
};
推荐阅读
- 数据结构|查找算法——二分查找（原理+源码）
- C++篇|【C++进阶】第十九篇——红黑树（概念+代码实现）
- Redis数据库|布隆过滤器原理
- 面试题目|面试题七 C/C++ 骑士营救公主 骑士只能向右或者向下移动，遇到陷阱就死了，求骑士营救公主的所有路线-程序员面试题
- 数据结构与算法|《程序员》算法擂台（骑士聚会）
- python|Yolo4-Tiny代码解读
- 算法|哈工大算法设计与分析总结
- Java学习之旅|【数据结构】 哈希表 详解
- 算法|JavaScript数据结构与算法 - 哈希表详解