Find median from large file of integers - Airbnb

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/find_median_in_large_file_of_integers/FindMedianinLargeIntegerFileofIntegers.java

Find the median from a large file of integers. You can not access the numbers by index, can only access it sequentially. And the numbers cannot fit in memory.

        private long search(int[] nums, int k, long left, long right) {
            if (left >= right) {
                return left;
            }

            long res = left;
            long guess = left + (right - left) / 2;
            int count = 0;
            for (int num : nums) {
                if (num <= guess) {
                    count++;
                    res = Math.max(res, num);
                }
            }

            if (count == k) {
                return res;
            } else if (count < k) {
                return search(nums, k, Math.max(res + 1, guess), right);
            } else {
                return search(nums, k, left, res);
            }
        }

        public double findMedian(int[] nums) {
            int len = 0;
            for (int num : nums) {
                len++;
            }

            if (len % 2 == 1) {
                return (double) search(nums, len / 2 + 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
            } else {
                return (double) (search(nums, len / 2, Integer.MIN_VALUE, Integer.MAX_VALUE) +
                        search(nums, len / 2 + 1, Integer.MIN_VALUE, Integer.MAX_VALUE)) / 2;
            }
        }
    }

https://instant.1point3acres.com/thread/159344https://instant.1point3acres.com/thread/159344
二分查找
思路就是：先找在INT_MIN和INT_MAX的median（0？），然后读large file of integers，找出比这个数小的个数是否有一半，然后调整二分的边界

其实有很多对大file的处理方法。 在interview当中，华人哥哥给出的hint是用binary search 首先， 我们知道对任何大的file median of any int will between INT_MIN and INT_MAX。所以我们知道了upper bound 和lower bound。我们猜一下median might be “guess = lower+(upper-lower)/2”。 之后我们可以验证对不对。就是扫一遍这个file，看看是不是有一半的element确实小于这个数字。如果是的话，这里注意一定要返回 smallest element in the file that is larger than the guess。如果有超过一半的数据小于这个guess，可想而知用binary search的方法，下一步就是移动上线到guess-1. 反之移动下线。对吧。那么这个算法最多需要scan 32次fille对不？这个数字当时我有点含糊。但是现在想想应该是对的。 

double findNth(int N, int left, int right) {
    while(left <= right){
        int guess = (left + right) / 2;
        int x, cnt = 0, next = right;
        while(x = readFile()) {
            if(x < guess) ++cnt;
            else next = min(next, x);
        }
        if(cnt == N - 1)
            return next;
        if(cnt < N - 1)
            left = guess;
        else
            right = guess - 1;
    }
    return 0.0;
}

double findMedian() {
    int len = 0;
    while(readFile()) ++len;
    if(len & 0x1) return findNth(len >> 1, INT_MIN, INT_MAX);
    int x = findNth(len >> 1, INT_MIN, INT_MAX);
    int y = findNth(1 + (len >> 1), x, INT_MAX);
    return double(x + y) / 2;
}