二分查找上界

1. 题目描述

请实现有重复数字的升序数组的二分查找。 输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数(指不存在大于等于查找值的数)，则输出数组长度加一。 输出位置从1开始计算

2. 思路

1. 思路一
   • 找第一个大于等于查找值的位置，可以通过先找到小于查找值的最大元素（即下界），然后往右走一步即可

3. 实现

package main

/**
 * 二分查找
 * @param n int整型 数组长度
 * @param v int整型 查找值
 * @param a int整型一维数组 有序数组
 * @return int整型
 */
func upper_bound_(n int, v int, a []int) int {
	//不存在这样的数字
	if a[n-1] < v {
		return n + 1
	}

	left := 0
	right := n
	for left < right {
		mid := left + (right-left)>>1
		if a[mid] < v {
			left = mid + 1
		} else if a[mid] > v {
			right = mid
		} else {
			right = mid
		}
	}

	return right + 1
}

4. 参考

• 二分查找_牛客题霸_牛客网