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!

• JollyJoker: I assume you're doing this mostly as an exercise, so not worth an answer by itself, but you could split the array in two and use Arrays.binarySearch()
• RedYoel: Yes i am. I know i can split it and use binary search and that way avoid some repeating code, does it have any other benefits besides it?
• JollyJoker: Mainly avoids implementing the search yourself, which could introduce bugs. Shorter code.
• Heslacher: Welcome to Code Review! I have rolled back your last edits. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• JollyJoker: Lol, nevermind, I"m an idiot. Of course splitting the array would require accessing it all, defeating the purpose of using binary search completely. Thought too much about "how" and not enough about "why"

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];
 }
}

• Peter Cordes: Since constructing an instance of this wrapper should be cheap (doesn't copy the array, just a reference), you could just do it on the fly for searching and not need to implement "lots of other methods" which would partially defeat the benefit you're getting from this. I guess Java doesn't have array "slices" that would let you take a view of the array that only includes elements 1..size-1 instead of 0..size-1, which would remove the need for an offset?
• D. Jurcau: Java's Collection.binarySearch expects a List which is quite a fat interface. A custom search method could do with a lighter interface that only provide get and size.
• Kartal Tabak: Instead of implementing java.util.List, you may extend java.util.AbstractList<Integer>. It has default implementations for all methods other than those two.

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);
}
```

• PhilipRoman: Returning a null Integer seems to be a bad idea, perhaps a special value, such as -1 would be better (which is what the standard library uses)
• Doi9t: In my opinion, all the choices are similar in this case, you can even throw an exception.
• Alexander: @PhilipRoman Almost certainly not. -1 is a very valid value (the sample input even contains negative numbers). This is what OptionalInt is for.

Answer 3

It seems you do not need those lines:

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

• greybeard: Welcome back to answering here... While I think your observation correct, do you have any advice what to do about it: what are the pros and cons of doing with or without those statements?
• RedYoel: @eagle i disagree actually, at least for the way the code is written right now.
• Peter Cordes: @RedYoel: You could try setting a breakpoint on those lines in a debugger and try to craft an input that reaches either of those statements, then after proving they're reached with some input, remove them to see if the function returns a wrong answer without them with the same input. Or the author of this answer could edit it to back up their assertion by explaining why those cases will already be handled earlier or later.