一个数的平方如果大于目标数，那么这个数一定不是目标数的平方根。这里，我们可以把二分的下界设置成0，上界粗略设置成目标值。每次只需要比较中位数 mid 的平方和 x 的关系即可。代码很好懂，
func mySqrt(x int) int { left, right := 0, x res := -1 for left <= right { mid := left + ((right - left) >> 1) if mid*mid <= x { res = mid left = mid + 1 } else { right = mid - 1 } } return res }
一看题目，这也能二分来解？
在我们的认知中，二分查找针对的对象是一个有序的集合，但是我们这个 demo 集合并不是有序的。为什么选这道题，是因为想带你们从不一样的角度看待二分。
我们在看待二分的时候往往会陷入到给定集合数据，或者陷入到二分就是利用集合的索引下标进行划分，我称之为确定二分的对象。
可是，根据上面的题意我们也可以确定二分的对象。
给定集合的整形范围在 1-n 之间，这不就是我们可以拆分的对象吗？
说人话！
给定集合的整形范围在 1-n 之间，可集合总数是 n+1，必然存在重复的数。那么我们只要每次取 n 的中位数，遍历集合，统计不大于中位数的个数，如果个数大于中位数，那就说明重复数肯定存在于中位数的左区间(包括n)，否则的话重复数必然出现在右区间。因此，当你能确定要对【什么】进行二分的时候，题目已经解了一半了。具体看代码，
func findDuplicate(nums []int) int { left, right := 0, len(nums)-1 res := -1 //结果 for left <= right { mid := left + ((right - left) >> 1) amount := 0 for j := 0; j < len(nums); j++ { if nums[j] <= mid { //统计不大于当前中位数的个数 amount++ } } if amount <= mid { // 如果统计个数不大于中位数，说明重复的值在右区间 left = mid + 1 } else { //否则重复值在左区间，并且包括中位数 res = mid right = mid - 1 } } //返回结果 return res }
我们可以看看这个算法的复杂度。首先二分本身的时间复杂度是 O(logN)。在二分的内部，有一个 for 语句，复杂度是 O(N)，故最终时间复杂度是O(NlogN)。空间复杂度O(1)。这道题有比二分更好的解法，至于其他更好的解法，可以自行研究。
