Binary search modification for "swaped" array

Question

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]) {
               if (arr[n] > 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];
                t = n;
                n = prevn + (n - prevn)/2;
                prevn = t;
            }
        }
        return arr[0] > arr[1] ? arr[arr.length - 1] : arr[0];
    }

    public static void main(String... args) {
        int[] arr = new int[args.length];
        for (int i = 0; i < args.length; i++)
            arr[i] = Integer.valueOf(args[i]);
        System.out.println(search(arr));            
    }
}

EDIT: the task is to find the lowest element

EDIT2: after much more thinking I boiled down my search function to this:

x = arr[arr.length - 1]
a = 0
b = arr.length
while b - a > 2
 if x > arr[(a+b)/2]
  b = (a+b)/2
 else 
  a = (a+b)/2
return arr[(a+b)/2]

the key point to simplification was to understand that middle element can always be calculated as (a+b)/2.

Answer 1

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 < hi) {
    mid  = low/2 + hi/2;
    if(isPivotIndex(arr,mid))
      return arr[mid];
    if(arr[hi-1] < arr[mid])
      low = mid + 1;
    else
      hi  = mid;
  }
  /* Array was actually sorted, either ascending or descending    */
  /* Note that return this covers corner cases of arr.length <= 3 */
  return max(arr[0], arr[arr.length-1]); 
}

int max(final int a, final int b) {
  return (a > 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 < arr.length-1) ? arr[index+1] : Integer.MAX_VALUE;
  return a <= b && b > c;
}

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

1. It immediately throws an exception on invalid input.

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

3. 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.

Answer 2

The midpoint caclulation as you have in your second edit suffers from a subtle bug, which only occurs when handling very large arrays.

int mid = (low + high) / 2;

There is a possibility for overflow here; a correct version would be:

int mid = low + ((high - low) / 2);

See http://googleresearch.blogspot.be/2006/06/extra-extra-read-all-about-it-nearly.html and https://bugs.java.com/bugdatabase/view_bug?bug_id=5045582

Answer 3

You initialize a certain value as x but you never update it - even though this value is completely arbitrary. Which means you are not really using it in the solution. This is a certain indication that your solution is wrong, and only works on the special case that you tested.

If the "pivot" point (i.e. the point where the the max value is followed by the min value) is in the left half of the array you will get a max value, and if it's in the right half you will get a min value.

i.e. if I input this array [10,11,12,1,2,3,4,5,6,7,8,9] it will return 12, but if I input this [5,6,7,8,9,10,11,12,1,2,3,4] it will output 1.

Problem Context

Searching a value in an array can be up to O(n) in time complexity - you have to iterate through the array and check for each element if it's equal the search value. But - if the array is sorted, this is reduced to O(log(n)) due to a strategy called Binary Search. Binary search allows us at each time cut half of the options to consider. You check the middle element in the array, if the search value is bigger you can discard the lower half, if it's lower you can discard the upper half, and now you do the same for the remaining array - until you either find the value or end up with an empty/1-element array - in that case the element is not in the array.

Here there is a problem that the array is swapped - the question is can we still reduce the time complexity to O(log(n)) ?

The key insight here is that even though the array itself is not perfectly sorted, at least half of it IS - and so we can always tell something about that half, and reduce our scope. This is true for every sub-division we make of the array - at least half of it will be sorted (and in some cases, both halves).

If we are looking for the min/max value, we basically don't care about the part that is sorted, because the pivot value will be in the other half (though the mid value should be included, as it can be the min/max value) - so we can discard the sorted part.

If we are looking for a specific value - we can automatically check if our value is in the range of the sorted half, if it is we discard the non-sorted half, and focus on the sorted. If it's not we focus on the non-sorted - and do the same.

Find Min value

Here is a solution in python - here we check if the right half is sorted. If it is, we reduce our scope to the left half. If not, we reduce our scope to the right half (note that in that case we can safely discard the mid point and move beyond it).

def findMin(arr):
    start = 0
    end = len(arr) - 1
    while(start < end):
        mid = (start + end) // 2
        rightSorted = arr[mid] < arr[end]
        if rightSorted:
            end = mid
        else:
            start = mid + 1
    return arr[start]

The decision to check the right is not arbitrary - it is necessary in case we search for a min value. If we instead search the left, and find out it is sorted - we could not confidently discard that half, as the array might be perfectly sorted - in that case the 0th element is the minimum. So we choose the right in order to be completely sure we still have the min value in the sub array.

Find Max value

In python this is actually very easy - you just need to go one element before the minimum - and even if the min is in 0 position, python interprets -1 as the last element of the array. So you could just use the same code as above, but with return arr[start-1].

Alternatively, we could reverse the min function above:

def findMax(arr):
    start = 0
    end = len(arr) - 1
    while(start < end):
        mid = (start + end) // 2
        leftSorted = arr[mid] > arr[start]
        if leftSorted:
            start = mid
        else:
            end = mid - 1
    return arr[start]

Finding a specific value

If we want to check if a specific value exists in the array - the same key insight hold.

def findVal(arr, val): 
    start = 0
    end = len(arr) - 1    
    while(start < end):
        mid = (start + end) // 2
        rightSorted = arr[mid] < arr[end] and arr[start] > arr[mid]
        if rightSorted:
            if val >= arr[mid] and val <= arr[end]:
                start = mid
            else:
                end = mid - 1
        else:
            if val >= arr[start] and val <= arr[mid]:
                end = mid
            else:
                start = mid + 1
    return val == arr[start]

A few differences: (1) we have to check if our value is in the sorted half, and if not discard it. (2) in order to avoid getting stuck with a sorted array of 2 elements - we have to define that the right half is sorted only if also the left half is not sorted (or vice versa). (otherwise we'll be stuck in an endless loop, as mid value won't advance)

[We could also create a less elegant implementation that simply goes until 2 elements and then just check if one of them is the value; or we could also always check the mid value and if it is the correct value return true, and if not we always discard it - I chose this implementation because I think it's more elegant and it is close to the other 2 min/max functions above]