Binary Search Upper Bound

1. Problem Description

Implement binary search on an ascending array that may contain duplicate values. Return the position of the first value greater than or equal to the target. If no such value exists, return the array length plus one. Positions are counted starting from 1.

2. Approach

1. Approach 1
   • To find the first position whose value is greater than or equal to the target, first find the largest element smaller than the target (the lower bound), then move one position to the right

3. Implementation

package main

/**
 * Binary search
 * @param n int array length
 * @param v int target value
 * @param a []int sorted array
 * @return int
 */
func upper_bound_(n int, v int, a []int) int {
	// No such value exists
	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. References

• Binary Search - NowCoder