题解 | #缺失数字#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 找缺失数字
     * @param a int整型一维数组 给定的数字串
     * @return int整型
     */
    public int solve (int[] a) {
        // write code here
        
        //方法一：暴力解法，时间复杂度为：O(n)
//         int length = a.length;
//         for(int i = 0;i<length;i++){
//             if(a[i]!=i){
//                 return i;
//             }
//         }
//         return length;
        
        //方法二：二分法，时间复杂度：O(logN)
        int length = a.length;
        int min = 0;
        int max = length - 1;//数组右边下标
        int mid = (min + max)/2;//数组左边下标
        while(min<=max){
            if(a[mid] > mid){
                max = mid - 1;
                mid = (min + max)/2;
            }else if(a[mid] == mid){
                min = mid + 1;
                mid = (min + max)/2;
            }
        }
        
        return max<0?mid:mid+1;
    }
}