287. 寻找重复数

struct Solution {}
impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        //区间都是闭区间,左右都包含
        let mut l = (1, (nums.len() / 2) as i32);
        let mut r = ((nums.len() / 2 + 1) as i32, (nums.len() - 1) as i32);
        loop {
            let result = Self::find_internal(nums.as_slice(), l, r);
            println!("l={:?},r={:?},result={:?}", l, r, result);
            //在左边,加1是因为闭区间
            if result.0 > l.1 - l.0 + 1 {
                let len = l.1 - l.0;
                if len == 0 {
                    //长度只有1表示找到了
                    return l.0;
                }
                r = (len / 2 + l.0 + 1, l.1);
                l = (l.0, len / 2 + l.0);
            } else {
                //在右边
                let len = r.1 - r.0;
                if len == 0 {
                    return r.0; //长度只有1表示找到了
                }
                l = (r.0, len / 2 + r.0);
                r = (len / 2 + r.0 + 1, r.1);
            }
        }
        // panic!("not found");
    }
    fn find_internal(nums: &[i32], l: (i32, i32), r: (i32, i32)) -> (i32, i32) {
        let mut countl = 0;
        let mut countr = 0;
        nums.iter().for_each(|i| {
            if *i >= l.0 && *i <= l.1 {
                countl += 1;
            }
            if *i >= r.0 && *i <= r.1 {
                countr += 1;
            }
        });
        (countl, countr)
    }
}