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));
 }
}