class Solution { public: /** * 二分查找 * @param n int整型 数组长度 * @param v int整型 查找值 * @param a int整型vector 有序数组 * @return int整型 */ int upper_bound_(int n, int v, vector<int>& a) { // write code here if(a[n-1] < v) return n + 1; //数组中所有数字都比给定的小,不存在,返回数组长度+1 int left = 0; int right = n - 1; while(left < right){ int mid = left + (right - left) / 2; //这样写防止溢出 if(a[mid] >= v) right = mid; else left = mid + 1; } return left+1; //本题输出的位置是从1开始计算的,但是我们的区间是用的数组下标,所以最后要输出left+1(right+1); } };用python写
时间: 2024-02-14 20:35:53 浏览: 23
class Solution:
def upper_bound_(self, n: int, v: int, a: List[int]) -> int:
if a[n-1] < v:
return n + 1
left = 0
right = n - 1
while left < right:
mid = left + (right - left) // 2
if a[mid] >= v:
right = mid
else:
left = mid + 1
return left + 1