3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What is the purpose of your algorithm? Is it suppose to locate an element in the semi-sorted array? Is it supposed to sort the semi-sorted array? Please improve your problem description so members of the community can intelligently provide suggestions/critiques for your code. \$\endgroup\$ – recursion.ninja Aug 10 '13 at 17:32
  • \$\begingroup\$ The task is to find the lowest element, but I think your comment for finding the highest element is still relevant. \$\endgroup\$ – dhblah Aug 12 '13 at 10:32
  • \$\begingroup\$ FYI, mid = (a+b)/2 risks integer overflow for large arrays. \$\endgroup\$ – recursion.ninja Feb 3 '14 at 15:40
5
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582

\$\endgroup\$
  • \$\begingroup\$ This is a great addition as your first post. But as you are referring to a whole well written article a simple comment might be a better way to share your knowledge here. +1 anyway for a good first post. \$\endgroup\$ – mheinzerling Aug 12 '13 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.