Searching an element in an alternately sorted array

Question

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 > bottomEven) {
        midEven = ((topEven + bottomEven) / 2);
        if (midEven % 2 != 0) {
            midEven++;
        }
        if (x > a[midEven]) {
            bottomEven = midEven + 1;
        } else if (x < a[midEven]) {
            topEven = midEven - 1;
        } else
            return midEven;
    }
    while (topOdd > bottomOdd) {
        midOdd = ((topOdd + bottomOdd) / 2);
        if (midOdd % 2 == 0) {
            midOdd++;
        }
        if (x > a[midOdd]) {
            topOdd = midOdd - 1;
        } else if (x < a[midOdd]) {
            bottomOdd = midOdd + 1;
        } else
            return midOdd;
    }
    return -1;
}

Thank you!

Answer 1

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 > 0) {
        List<Integer> sortedAscending = new EverySecondElement(haystack, 0);
        int index = Collections.binarySearch(sortedAscending, needle);
        if (index >= 0) return index * 2;
    }
    if (haystack.length > 1) {
        List<Integer> sortedDescending = new EverySecondElement(haystack, 1);
        int index = Collections.binarySearch(sortedDescending, needle, Comparator.reverseOrder());
        if (index >= 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<Integer> {
    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];
    }
}

Answer 2

here are some suggestions for your code.

1) Since the array is not updated, I suggest that you extract the size in a variable.

public static int find(int[] a, int x) {
    //[...]
    int arrLength = a.length;
    //[...]
}

2) In my opinion, there's no gain to check if the boundaries are the current value, since the value can be anywhere.

else if (a[0] == x) {
    return 0;
} else if (a[topOdd] == x) {
    return topOdd;
}

3) I suggest that you move the check for the size before the variables, it will remove the calculation of the other variables when the array is empty.

int arrLength = a.length;

if(arrLength == 0) {
    return -1;
}

int topEven = arrLength - 1;
int topOdd = arrLength - 1;
int bottomEven = 0;
int midEven = 0;
int bottomOdd = 1;
int midOdd = 0;

if (a[0] == x) {
    return 0;
} else if (a[topOdd] == x) {
    return topOdd;
}

4) I suggest that you add the parentheses on the else, since it make the code harder to read, in my opinion.

5) I suggest that you make function to check if the number is odd or even.

    private static boolean isEven(int value) {
        return value % 2 != 0;
    }

    private static boolean isOdd(int value) {
        return !isEven(value);
    }

6) I suggest that you extract the loop parts in methods.

public static int find(int[] a, int x) {
    //[...]
    int maxLastArrayPosition = arrLength - 1;

    Integer evenPosition = findNumberEven(a, x, maxLastArrayPosition);
    if (evenPosition != null) {
        return evenPosition;
    }
    //[...]
}

private static Integer findNumberOdd(int[] a, int x, int maxLastArrayPosition) {
    int topOdd = maxLastArrayPosition;
    int midOdd = 0;
    int bottomOdd = 1;
    while (topOdd > bottomOdd) {
        midOdd = ((topOdd + bottomOdd) / 2);

        if (isOdd(midOdd)) {
            midOdd++;
        }

        if (x > a[midOdd]) {
            topOdd = midOdd - 1;
        } else if (x < a[midOdd]) {
            bottomOdd = midOdd + 1;
        } else {
            return midOdd;
        }
    }

    return null;
}

7) I suggest that you make a constant for the invalid value.

 public static final int INVALID = -1;

Refactored code

public static final int INVALID = -1;

public static int find(int[] a, int x) {
    int arrLength = a.length;

    if (arrLength == 0) {
        return INVALID;
    }

    int maxLastArrayPosition = arrLength - 1;

    Integer evenPosition = findNumberEven(a, x, maxLastArrayPosition);
    if (evenPosition != null) {
        return evenPosition;
    }

    Integer oddPosition = findNumberOdd(a, x, maxLastArrayPosition);
    if (oddPosition != null) {
        return oddPosition;
    }

    return INVALID;
}

private static Integer findNumberOdd(int[] a, int x, int maxLastArrayPosition) {
    int topOdd = maxLastArrayPosition;
    int midOdd = 0;
    int bottomOdd = 1;
    while (topOdd > bottomOdd) {
        midOdd = ((topOdd + bottomOdd) / 2);

        if (isOdd(midOdd)) {
            midOdd++;
        }

        if (x > a[midOdd]) {
            topOdd = midOdd - 1;
        } else if (x < a[midOdd]) {
            bottomOdd = midOdd + 1;
        } else {
            return midOdd;
        }
    }

    return null;
}

private static Integer findNumberEven(int[] a, int x, int maxLastArrayPosition) {
    int topEven = maxLastArrayPosition;
    int midEven = 0;
    int bottomEven = 0;
    while (topEven > bottomEven) {
        midEven = ((topEven + bottomEven) / 2);
        if (isEven(midEven)) {
            midEven++;
        }
        if (x > a[midEven]) {
            bottomEven = midEven + 1;
        } else if (x < a[midEven]) {
            topEven = midEven - 1;
        } else {
            return midEven;
        }

    }

    return null;
}

private static boolean isEven(int midEven) {
    return midEven % 2 != 0;
}

private static boolean isOdd(int value) {
    return !isEven(value);
}

```

Answer 3

It seems you do not need those lines:

} else if (a[0] == x) {
    return 0;
} else if (a[topOdd] == x) {
    return topOdd;