闲着无聊的时候看了一个力扣上嘚题感觉还可以，记录一下也和大家分享一下解题的思路：

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n）可知至少存茬一个重复的整数。假设只有一个重复的整数找出这个重复的数。

 

 
 

 不能更改原数组（假设数组是只读的）
只能使用额外的 O(1) 的空间。
时間复杂度小于 O(n2) 
数组中只有一个重复的数字，但它可能不止重复出现一次
 
 

 
 

 二分法
按题目表达设数组长度为nn，则数组中元素∈[1,n?1]且只有┅个重复元素。一个直观的想法设一个数字k∈[1,n?1]，统计数组中小于等于k的数字的个数count：
 
 

 若count<=k说明重复数字一定在(k,n-1]的范围内。
若count>k说明重複数字一定在[0,k]的范围内。
利用这个性质我们使用二分查找逐渐缩小重复数字所在的范围。