Binary search modification for "swaped" array

I was making an algorithm for a task I found in a book. It says that there is sorted array, that was swapped so it looks like "4567123", and was proposed to use binary search modification.

Below is my solution in java.

The thing is, I'm a bit cringed that I can't process cases for array size of 2, 3 generically (for case of size 1 it's obvious that it'll require a specific case). Not that I need a solution that'll do that generically for 2, 3 array size cases. But I more like to know, is it a problem. Also I addressed a problem when array wasn't swaped at all. And I'm not sure that I should've done this, if preconditions are clearly specified. Btw binary search doesn't check that it's input is sorted.

So, more what I need is not code review itself, but more of advise, is my hardcoded cases and support for nonswaped array is good or bad. I myself believe that cases are fine, as algorithm compares 2 values, and thus requires at least 2 values to be compared, also it searches for the "peak and drop". But I'll probably try to modify it so it won't cover non-swaped array case and generically work for 2, 3 size array.

```
//file SwapedArraySearch.java\
public class SwapedArraySearch {
public static int search(int[] arr) {
switch (arr.length){
case 1:
return arr[0];
case 2:
return arr[0] > arr[1]?arr[1]:arr[0];
case 3:
return arr[0] > arr [1] ? (arr[1] > arr[2]?arr[2]: arr[1]):
(arr[0] > arr[2]?arr[2]: arr[0]);
}
int x = arr[0];
int n = arr.length/2;
int prevn = arr[n] > x ? arr.length -1 : 1;
int t;
while(prevn != n) {
if (x arr [n + 1] )
return arr[n+1];
t = n;
n = n + (prevn - n)/2;
prevn = t;
} else {
if (arr[n - 1] > arr[n])
return arr[n];

General Advise

-
Your methods are difficult to read because you chose to use predominantly single character variable names. Multi-character descriptive variable names are much easier to associate with a value, making the code magnitudes easier to read & maintain. Also, when implementing a binary search it is typical to use hi, lo & mid as variable names.

-
Whenever you nest a ternary statements, this should be an immediate red flag, that you are not writing clear & maintainable code. As soon as you write a nested ternary statement I would advise you to pause, and consider what functionality you are trying to achieve and consider different ways to express that functionality. I'm not going to say that nested ternary statements are always a sign that your doing something wrong, but nested ternary statements is always a sign you should stop and think about what your doing.

Algorithmic Advise

I am assuming the algorithm is locating the largest element in a semi-sorted array that has two (and only two) distinctly sorted sequences with a pivot index contains largest value in the array.

-
The three conditions in your switch case are, generally doing the same thing. Each case is returning the largest element in a the array, but can't use the loop because the array is too small. We can cover these conditions in the final return.

-
You should also check for general error cases such as null or the empty set (new int[0]) being passed into the function.

-
Since the logic for checking if the current value of the binary search is the pivot index contains a lot of logic to do correctly, I would create a method isPivotIndex().

Putting all that together, your solution could look something like this.

Java Code: (ideone example link)

int findLargestValueInSemiSortedArray(int arr[]) {
  if(arr==null || arr.length==0)
    throw new IllegalArgumentException();

  int hi  = arr.length; /* exclusive upper bound */
  int low = 0;          /* inclusive lower bound */
  int mid;
  while(low  b) ? a : b;
}

boolean isPivotIndex(final int[] arr, final int index) {
  int b = arr[index];
  int a = (index > 0) ?            arr[index-1] : Integer.MAX_VALUE;
  int c = (index  c;
}

The above is much more readable, has fewer lines of code, and is easier to check for correctness.

-
It immediately throws an exception on invalid input.

-
It uses isPivotIndex() method to isolate complex logic & maintain a single level of abstraction.

-
It uses a clever final return to handle corner cases.

Let's consider how the final return covers the corner cases in your original switch statement.

Case 1: (arr.length == 1)

• max(arr[0],arr[arr.length-1]) will compare the same values and return arr[0].

Case 2: (arr.length == 2)

• max(arr[0],arr[arr.length-1]) will evaluate exactly the same as your ternary statement.

Case 3: (arr.length == 3)

• max(arr[0],arr[arr.length-1]) will return the larger of arr[0] and arr[2]. If arr[1] happened to be the max value it would have been the pivot index in the binary search loop and the method would have already returned.

StackExchange Code Review Q#29090, answer score: 6