Searching an element in an alternately sorted array I had to write some code that receives a number 'x' and an alternately sorted array (an array with all even indexes sorted upwards and all odd indexes sorted downwards) and checks if 'x' exists in the array. If it exists, the method will return the index, if not, the method will return -1.


If there is more than one 'x' in the array, I can choose which one to return.
An array example: {-3, 10, 0, 9, 2, 5, 3, 0, 6, -5}


I've written the following code, and I will like to hear what you think, how I can improve it, and if you think of some cases when it won't work: 

public static int find(int[] a, int x) {
    int topEven = a.length - 1, topOdd = a.length - 1, bottomEven = 0, midEven = 0, bottomOdd = 1, midOdd = 0;
    if (a.length == 0) {
        return -1;
    } else if (a[0] == x) {
        return 0;
    } else if (a[topOdd] == x) {
        return topOdd;
    }
    while (topEven &gt; bottomEven) {
        midEven = ((topEven + bottomEven) / 2);
        if (midEven % 2 != 0) {
            midEven++;
        }
        if (x &gt; a[midEven]) {
            bottomEven = midEven + 1;
        } else if (x &lt; a[midEven]) {
            topEven = midEven - 1;
        } else
            return midEven;
    }
    while (topOdd &gt; bottomOdd) {
        midOdd = ((topOdd + bottomOdd) / 2);
        if (midOdd % 2 == 0) {
            midOdd++;
        }
        if (x &gt; a[midOdd]) {
            topOdd = midOdd - 1;
        } else if (x &lt; a[midOdd]) {
            bottomOdd = midOdd + 1;
        } else
            return midOdd;
    }
    return -1;
}


Thank you!
How about an alternate approach: instead of adapting the binary-search algorithm to work with all kinds of alternate sorted collections, how about adapting the collections to be able to run classic binary search on them.

This enables one to use production ready searching methods without reinventing the wheel and risking bugs. Even if one decides to rewrite binary search as an exercise it is still easier as it doesn't have to take the alternating indexes into account.

public static int findInAlternateSortedArray(int[] haystack, int needle) {
    if (haystack.length &gt; 0) {
        List&lt;Integer&gt; sortedAscending = new EverySecondElement(haystack, 0);
        int index = Collections.binarySearch(sortedAscending, needle);
        if (index &gt;= 0) return index * 2;
    }
    if (haystack.length &gt; 1) {
        List&lt;Integer&gt; sortedDescending = new EverySecondElement(haystack, 1);
        int index = Collections.binarySearch(sortedDescending, needle, Comparator.reverseOrder());
        if (index &gt;= 0) return index * 2 + 1;
    }
    return -1;
}


All that is needed to be able to use the standard library provided Collections.binarySearch is to provide two views into the original array, as if he had two independently sorted collections.

Given an index into each of these lists, we can easily calculate the index from the original array from where to fetch an element in \$\mathcal{O}(1)\$ time, thus the runtime of the entire search is still \$\mathcal{O}(\log N)\$.

static class EverySecondElement extends AbstractList&lt;Integer&gt; {
    private int[] array;
    private int offset;

    EverySecondElement(int[] array, int offset) {
        this.array = array;
        this.offset = offset;
    }

    @Override
    public int size() {
        return (array.length - offset + 1) / 2;
    }

    @Override
    public Integer get(int index) {
        return array[offset + index * 2];
    }
}