【leetcode

URL题目分析源码源码概述小结

链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/

#include 

int singleNonDuplicate(int *nums , int nums_size){
    int low = 0, high = nums_size - 1;

    while(low < high){
        int mid = (high - low)/2 + low;
        
        if (nums[mid] == nums[mid ^ 1]) {  // tips
            low = mid + 1;
        } else {
            high = mid;
        }   
    }   

    return nums[low];
}

int main(){
    int num = 0;

    int arr1[] = {1,1,2,3,3,4,4,8,8};
    int size_arr1 = sizeof(arr1)/sizeof(arr1[0]);
    printf("arr =  ");
    for (int i = 0;i < size_arr1; i++)
        printf("%d,",arr1[i]);
    num = singleNonDuplicate(arr1 , size_arr1);
    printf("nnum = %dn ",num);

    int arr2[] = {3,3,7,7,10,11,11};
    int size_arr2 = sizeof(arr2)/sizeof(arr2[0]);
    printf("arr =  ");
    for (int i = 0;i < size_arr2; i++)
        printf("%d,",arr2[i]);
    num = singleNonDuplicate(arr2 , size_arr2);
    printf("nnum = %d n ",num);

    return 0;
}

arr =  1,1,2,3,3,4,4,8,8,
num = 2
arr =  3,3,7,7,10,11,11,
num = 10 

二分法，判断左右边界，数组有序，得mid为偶数位时，mid + 1 = mid⊕1；mid位奇数位时，mid - 1 = mid⊕1

有序数组，搜索，二分法。
注意按位亦或的操作，数据处理的细节问题，还有一个题目是通过位比较的题目我忘记题号了，那一题我觉得很经典。