leetcode-go/leetcode/medium/287.find-the-duplicate-number.go

func findDuplicate(nums []int) int { // Binary search
	n := len(nums)
	beg, end := 1, n
	for beg < end {
		mid := (beg + end) / 2
		cnt := 0
		for i := 0; i < n; i++ {
			if nums[i] <= mid {
				cnt++
			}
		}
		if cnt <= mid {
			beg = mid + 1
		} else {
			end = mid
		}
	}
	return beg
}