给出一个顺序文件，它最多包含40亿个随机排列的32位整数 问题：找出一个不在文件中的32位整数。_JAVA_编程开发_程序员俱乐部

class="java" name="code">

package com.myway.study;

import java.util.ArrayList;
import java.util.List;

/**
 * 给出一个顺序文件，它最多包含40亿个随机排列的32位整数

        问题：找出一个不在文件中的32位整数。
 * User: zhangyong
 * Date: 14-5-17
 * Time: 下午12:38
 * To change this template use File | Settings | File Templates.
 */
public class BinarySearchNoExist {

    public static Integer lostNum(int arr[], int len, int maxBits) {

        List lostNumList = new ArrayList();

        int lostNum = 0;

        int MASK = 0;

        int locZero = 0;

        int locOne = 0;

        int[] arrZero = new int[len];

        int[] arrOne = new int[len];

        for (int bit = maxBits - 1; bit >= 0; bit--) {

            locOne = 0;
            locZero = 0;

            MASK = 1 << bit;
            for (int i = 0; i < len; i++) {
                if ((arr[i] & MASK) == MASK) {
                    arrOne[locOne++] = arr[i];
                } else {
                    arrZero[locZero++] = arr[i];
                }
            }

            if ((locOne == MASK) && (locZero == MASK)) {

            } else {
                if (locOne > locZero) {
                    arr = arrZero;
                    len = locZero;
                } else {
                    lostNum += MASK;
                    arr = arrOne;
                    len = locOne;
                }
            }
        }

        return lostNum;
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 3, 5, 7, 10, 9, 11, 12, 14};
        System.out.println(lostNum(arr, arr.length, 4));
    }

}