package arrays;

/**题目：有序数组中的单身数字
 *
 * @Author Gavin
 * @date 2022.01.03 10:54
 */
public class array_11 {
    /**
     * 第一种方法 ：循环所有的元素进行异或操作，略
     * Time:O(n)
     */
    /**
     * 第二种方法：利用有序这个特点使用二分搜索法
     */
    //Time:O(log(n)) Space:O(1)
    public static int solution(int[] nums){
        int low=0,high=nums.length-1;
        while (low<=high){
            int mid=low+(high-low)/2;
            if(mid-1>=0&&nums[mid-1]==nums[mid]){
                --mid;
            }else if(mid+1<=high&&nums[mid+1]==nums[mid]){}
            else{
                return nums[mid];
            }
            /**
             * 这里就是核心点：
             * 因为单身数字都不是成对出现的，所以有一边是为奇数
             */
            if((mid-low)%2==1)high=mid-1;
            else low=mid+2;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array=new int[]{2,2,3,3,4};
        System.out.println(solution(array));
    }
}