解释一下
比如给两个数组
数组１：[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

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

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的初始值就好了.

李康好帅

y总 int mid = l + r >> 1;这句是简写了吗 看不明白 还有定义x和s的作用是什么呢

>> 是右移，这句等同于int mid = (l+r)/2；s计算数组里值处于[l, mid]这个区间的元素个数（也就是满足l<=x<=mid的x的个数）

用二分查找的想法来思考，区间为[1,n]，只考虑[1,m]中的数字没有重复，考虑[m+1,n]中的数字有重复。查找的就是最小的m使得在原数组中有重复。