Using binary search for finding the number that appears odd number of times in an array of numbers

Question

I am able to do it for my first example but for example 2, I am not able to get the right answer. My code actually looks for the middle position and traverse the array to the right side of the array as mid -1 = mid, which makes the condition true but mid -1 = mid -2. What should I do for ignoring this?

 import java.util.Arrays;

class Lab4 {
// Function to return k'th smallest
// element in a given array


public static int findOddNumber(int[] numbers, int startIndex, int endIndex) {

    int mid = 0;
    mid = (startIndex + endIndex) / 2;

    if (startIndex == endIndex) {
        return numbers[startIndex];
    }
    if (mid % 2 == 0) {
        if (numbers[mid] == numbers[mid + 1]) {
            return findOddNumber(numbers, mid + 2, endIndex);
        } else {
            return findOddNumber(numbers, startIndex, mid);
        }
    } else {
        if (numbers[mid] == numbers[mid - 1])
            return findOddNumber(numbers, mid + 1, endIndex);
        else
            return findOddNumber(numbers, startIndex, mid - 1);
    }
}

// driver program
public static void main(String[] args) {


    int arr2[] = new int[] { 1, 1, 2, 3, 3, 5, 5 };
    System.out.println("Odd number is " + findOddNumber(arr2, 0, arr2.length - 1));

    int arr3[] = new int[] { 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6 };
    System.out.println("Odd number is " + findOddNumber(arr3, 0, arr3.length-1));

    }

}

Answer 1

Sorry I understand your solution now. One of the problems is that just by looking at the element to the right or the left of mid you still can't know which way to go. So here is an adaption: Find the last index with the same value as the value for mid using binary search. If it is odd, then you have to search in the subarray right of that index, otherwise you have to look on the left side. Time complexity O((logn)^2), but only works for ordered arrays with exactly one element appearing an odd number of times. In code:

public static int findOddNumber(int[] numbers, int startIndex, int endIndex) {
    if (numbers[startIndex] == numbers[endIndex])
        return numbers[startIndex];
    int mid = (startIndex + endIndex) / 2;
    int last = findLast(numbers, mid, endIndex);
    if (last % 2 == 1)
        return findOddNumber(numbers, last + 1, endIndex);
    else
        return findOddNumber(numbers, startIndex, mid - mid % 2);
}

private static int findLast(int[] numbers, int startIndex, int endIndex) {
    if (numbers[startIndex] == numbers[endIndex])
        return endIndex;
    int mid = (startIndex + endIndex) / 2;
    if (numbers[startIndex] == numbers[mid])
        return findLast(numbers, mid, endIndex - 1);
    else
        return findLast(numbers, startIndex, mid - 1);
}

---

For unordered arrays there are much simpler ways to find all the odd numbers using a hash set. This also works for multiple odd numbers. Just go through the array and if a number is already in the set remove it otherwise add it. In the end you have all numbers that appear an odd number of times in the hash set. This takes O(n) time and space.

If you know that there is exactly one number appearing an odd number of times, then you can just xor all the array values and get the solution. O(n) time and O(1) space. This also works for unordered arrays.