谢谢，很有帮助。让我体会到了智商被碾压的感觉。

解释一下
比如给两个数组
数组１：[1,2,3,4,5,6,7,7] 重复数字是7
数组２：[1,1,2,3,4,5,6,7] 重复数字是1

将数值1－７分成两个区间
区间１｛１，２，３，４｝，长度为４
区间２｛５，６，７｝，长度为３
以数组２：[1,1,2,3,4,5,6,7] 为例
数组数值落在区间１的数据为{1,1,2,3,4}，个数超过区间长度
落在区间２的数值为｛5,６,７｝，个数和区间长度相等
因此重复数据必然位于区间１上

再次将区间１二分
区间１｛１，２｝
区间２｛３，４｝

分析同上

代码有一股优乐美的味道

哈哈哈优乐美

此题中

r = nums.size()

也可以ac。

感觉这样合理些， “nums.size() - 1”实在没想明白。

题目中的n+1就是数组长度，就是nums.size()，数组中数据取值1~n，就是1~nums.size()-1

果然题越辩越明。一语中的，终于看懂了，感谢感谢～

不懂就问，一开始为啥L赋初值为1呢

为啥R赋初值为size-1呢

1~size()也可以哎

因为题目中说了数组内的每个值的取值范围是 1~n，所以 L 一开始赋值为 1 ；

因为题目中说数组中元素的个数是 n + 1，而每个元素最大只有 n ，所以 R = size - 1；

OK明白了感谢

一开始有个地方没想明白,就是为什么一定要往数的个数大于坑的个数的一侧去二分, 因为我想的是另一侧也可能出现重复数字,比如数的总个数为10, 数字2出现2次,但是3和4都不出现, 相当于一个坑上多出现的一个数字,被另外的坑一个数都没有,给抵消了,这样这一侧的区间数字个数也会小于坑的个数,但也有可能存在重复数字.

这个想法其实没啥问题,但是题目只需要求出任意一个重复数字, 若是上面的情况,那么这一侧空出来的这些坑,一定会在另一侧得到填补,因为数字的总个数是固定的, 这边的数字没出现,那么另一侧数字就一定会多.

比如 n + 1 = 11, 我们先构造出 [1,2,2,5, ? ? ? ], 第一次二分 mid = 5, 可见5的左侧是存在重复元素的,但是这一侧的数字个数只有4,是小于坑位的, 但是继续构造原数组就会发现, 5 的右侧的数字一定会多出来,比如 [1,2,2,5,6,7,8,9,10, x, x] , 多出来的两个数(用x)表示, 一定只能从 大于 5 的数字里面选,一定会构成重复.

所以,往 数字个数大于坑位数量的一侧去寻找,始终是能找到重复数字的,只是,另一侧可能也会存在重复数字.

y总，我将这句循环拆解之后得到的结果有问题啊。

//for (auto x : nums) s += x >= l && x <= mid;
            for (auto x : nums)
            {
                if (x >= 1 && x <= mid)
                    s ++;
            }
//测试数据：[1, 7, 5, 9, 7, 9, 5, 1, 5, 6, 7]
//输出：6
//答案：7

我知道了，是 x >= l,不是1（一），代码里面太像了，看饿了半天都没看出来。。。

感谢！我犯了一样的问题

x>=L 而不是1

s += x >= l && x <= mid;这句什么意思没看懂，之前没这么写过

若x>=l且x<=mid，则s+1

哦哦就是说他应该是s+=(x>=l&&x<=mid)这样看对吧，懂了谢谢啦

对的，你可以试一下68.0到n-1中缺失的数字，也可以这样做

为什么这题y总的代码在力扣过不了

厉害厉害

good

真优雅

y总代码太优美了

y总我的神

按道理来说你这写法是左闭右开的写法，维持[1,n]区间必须要初始化[1,n+1)才符合逻辑，但是我试了试开始AC了，还有跳出循环后必然 l >= r，但是题目分析区间长度缩为1必须要 l = r才行，但是我想证明下二分跳出循环是否有可能 l > r吗

按[1,n+1)初始化来调试各种数组长度二分后跳出循环必然是 l = r，这个结论应该为真，但是需要想想证明。

这个写法我刚开始看一眼模糊，两种写法混杂一起。按左闭右闭区间[1,n]初始化,循环条件 l < r 又是左闭右开的写法，循环内的赋值 r = mid 也是左闭右开的写法，
跳出循环居然能 l = r 刚好符合长度为1，这就是所谓的错错得正

看来是我着相了，想着各种左闭右开的写法等等。

#include <algorithm>
#include <iostream>
using namespace std;
// 该二分写法区间的定义是左闭右开[l,r]
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r) {// l<r 为了跳出循环得到 l=r
            /*
              划分的区间：[l, mid], [mid + 1, r]
              必然有赋值 r = mid 与 l = mid+1 为了不陷入死循环必然 mid = l + ((r - l) >> 1)
              循环内按区间[l, mid]维护

              划分的区间：[l, mid-1], [mid, r]
              必然有赋值 r = mid-1 与 l = mid 为了不陷入死循环必然 mid = l + ((r - l + 1) >> 1)
              循环内按区间[l, mid-1]维护

              思考链路: 跳出循环想得到 l=r -->循环条件必然 l < r
              想按[l, mid], [mid + 1, r]划分区间-->赋值情况必然是 r = mid 与 l = mid+1-->不想陷入死循环必然需要这样计算mid: mid = l + ((r - l) >> 1)

              由果溯因,差不多就是这意思, 想要什么,必然需要这样做。
             */
            int mid = l + ((r - l + 1) >> 1); // 闭区间两种写法都一样 mid = l + ((r - l+1) >> 1)  ,划分的区间：[l, mid], [mid + 1, r]
            int s = 0;
            for (auto x : nums) s += x >= l && x <= mid-1;  // [l,mid-1]
            if (s > mid -1 - l + 1) r = mid-1;  //[l,mid]
            else l = mid; // [mid+1,r]
        }
        return r;
    }
};

这里的区间长度是这个区间可以有多少整数

int mid=1+r>>1中的两个‘>>’号是什么意思啊

除2

右移

class Solution {
public:
int duplicateInArray(vector[HTML_REMOVED]& nums) {
int l=1,r=nums.size()-1;
while(l[HTML_REMOVED]>1;
int s=0;
for(auto x:nums) s=s+(x>=mid&&x<=r);
if(s>r-mid+1) l=mid+1;
else r=mid;
}
return r;

 }

};
为什么我这样写不行啊

for (auto x : nums)是啥意思啊

遍历nums数组，auto是cpp关键字，自动获取数据类型

理解了，非常感谢

s > mid - l + 1这个判断条件是什么意思啊没看懂

mid-l+1就是左半区间[l,r]的元素个数，比如2,3,4有4-2+1个数

如果是0~n-1的范围该怎么修改呢？

这个还是N个数啊,跟数组下标没关系, 这个是按照数值来分组的, 也就是说 l = 0, r = nums.length - 2, 然后按照上面的思路对数值的范围二分, 一定会有一组里面数字的个数大于组数字的长度(组长), 例如(n = 24, 一共有 25个位置, 每个数的范围是 [0, 23], 也就是说第一次的mid = 12, 左边组长为13, 右边组长为11, 这才24个数字, 所以说, 左边或者右边的组里面一定会有重复的数字

也就是说, 你只需要, 修改 l 和 r的初始值就好了.