LC 287 Find the Duplicate Number 二分查找的方法看不懂

题目是：
https://leetcode.com/problems/find-the-duplicate-number/
public int findDuplicate(int[] nums) {            int low = 1, high = nums.length - 1;   
    while (low <= high) {        
        int mid = (int) (low + (high - low) * 0.5);        
        int cnt = 0;        
        for (int a : nums) {            
            if (a <= mid)
           ++cnt;        
        }        
        if (cnt <= mid)
            low = mid + 1;        
        else high = mid - 1;   
    }   
    return low;
}
这个答案看不懂，没有任何头绪，求指点

public int findDuplicate(int[] nums) {  
           int low = 1, high = nums.length - 1;   
    while (low < high) {    // this should be low < high, so when low = high, the index is the target we want.   
        int mid = (int) (low + (high - low) * 0.5);        
        int cnt = 0;        
        for (int a : nums) {            
            if (a <= mid) // count the number of elements not larger than mid.
           ++cnt;        
        }        
        if (cnt <= mid) // if the number no larger than mid, there are no duplicates for the number not larger than mid
        // since if there is, for the number larger than mid, there must also be a duplicated number(or else it cannot have enough element)
        // which breaks the rule for only one duplicated number.
            low = mid + 1;        
        else high = mid;   // for the opposite, since there must be a duplicate for the number no larger than mid, the number larger than mid shall be excluded.
        // it is impossible that the duplicated number is larger than n.
        // I think it is rather "high = mid" since the mid may also be the possible target.
    }   
    return low;
}

CNT代表的是小于等于mid的数的个数，如果cnt < mid表明重复的数不再[low, mid]之间, 自然 low = mid +1，剩下的分析类似。另外注意看题目，如果数组的长度是n，能选得数只能实在【1，n-1】之间，且重复的数只有一个，这道题的bs是基于这两个特定条件的。

susie_91 发表于 2016-9-14 14:58
LZLZ还在吗，我看你usc申了3个program，EE, DTIN, CSES，其中dtin和cses是？？？

前面那个好像叫data informatics，后面那个就是Computer Science (Engineer & Scientist)，我们俗称的转专业37学分项目

抱歉，直接粘贴过来的答案没有排好版，这是答案的链接
https://discuss.leetcode.com/top ... using-binary-search

indpoor 发表于 2016-8-16 11:00
CNT代表的是小于等于mid的数的个数，如果cnt < mid表明重复的数不再[low, mid]之间, 自然 low = mid +1，剩 ...

明白了，之前把low跟high错认为是index了，感谢

LZLZ还在吗，我看你usc申了3个program，EE, DTIN, CSES，其中dtin和cses是？？？

南方Giraffe 发表于 2016-9-14 21:35
前面那个好像叫data informatics，后面那个就是Computer Science (Engineer &amp; Scientist)，我们俗称的转 ...

好哒 谢谢 di还收转专业的啊！很少报这个转专业的录取哎地里

楼主楼主，最后你饭大和CMU-SV spring选了哪一个呀

Eric_Wenyi 发表于 2016-10-6 06:47
楼主楼主，最后你饭大和CMU-SV spring选了哪一个呀

最后秋季去了NYU-Courant 然后准备转去SV