Searching an element in an alternately sorted array
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];
    }
}