Single Element in a Sorted Array, thesarfo

Every number in a sorted array appears twice except one — find it.

Brute force: the single element is the only one where neither arr[i-1] nor arr[i+1] equals it (with edge handling for the first/last index).

public static int solution(int[] arr){
    if (arr.length == 1) return arr[0];

    for(int i = 0; i < arr.length; i++){
        if(i == 0){
            if(arr[i] != arr[i + 1]) return arr[i];
        } else if(i == arr.length - 1){
            if(arr[i] != arr[i - 1]){
                return arr[i];
            }
        } else{
            if(arr[i] == arr[i-1] && arr[i] == arr[i + 1]){
                return arr[i];
            }
        }
    }
    return -1;
}

Alternative brute force — XOR: a ^ a = 0 and a ^ 0 = a, so XOR-ing every element together cancels out all the pairs and leaves only the single value.

public static int solution(int[] arr){
    int ans = 0;

    for(int i = 0; i < arr.length; i++){
        ans = ans ^ arr[i];
    }
    return ans;
}

Optimal — binary search: duplicate pairs follow an index parity pattern. Before the single element, a pair starts at an even index (arr[i] == arr[i+1] when i is even). After the single element, that flips (arr[i] == arr[i-1] when i is even). So at mid, check which pattern holds to decide which half to eliminate.

public static int singleNonDuplicate(int[] arr) {
    int n = arr.length;

    if (n == 1) return arr[0];
    if (arr[0] != arr[1]) return arr[0];
    if (arr[n - 1] != arr[n - 2]) return arr[n - 1];

    int low = 1, high = n - 2;
    while (low <= high) {
        int mid = (low + high) / 2;

        if (arr[mid] != arr[mid + 1] && arr[mid] != arr[mid - 1]) {
            return arr[mid];
        }

        // We are in the left half (duplicate pair pattern intact):
        if ((mid % 2 == 1 && arr[mid] == arr[mid - 1]) ||
            (mid % 2 == 0 && arr[mid] == arr[mid + 1])) {
            low = mid + 1; // eliminate left half
        }
        else {
            high = mid - 1; // eliminate right half
        }
    }

    return -1; // should never reach here
}