Binary search in rotated sorted array

Question

Looking for code review, optimizations, good practice recommendations etc.

/**
 * This is utility class for operations on rotated one-d array.
 * 
 * Note: a sorted array, reverse-sorted or a single element is array is not considered rotated sorted.
 * Eg:
 * [4, 5, 1, 2, 3] is condidered rotated.
 * While.
 * [1, 2, 3, 4, 5] is not considered rotated
 * 
 * 
 * Complexity: O (log n)
 */
public final class RotatedOneDSortedArray {

    private RotatedOneDSortedArray() { }

    /**
     * Searches for the value provided in the rotated sorted array.
     * If found, returns the index, of provided array, else returns -1.
     * If array is not rotated and sorted, then results are unpredictable
     * 
     * Throws an exception if array is null.
     * 
     * @param a the rotated sorted array
     * @param x the element to be searched
     * @returns the index at which the element is found, else returns -1
     */
    public static int binarySearchForRotatedArray(int[] a, int x) {
        int partitionIndex = findPartition(a, 0, a.length - 1);

        if (partitionIndex == -1) return -1;

        if (x >= a[0] && x <= a[partitionIndex]) {
            return binarySearch(a, 0, partitionIndex, x);
        } else {
            return binarySearch(a, partitionIndex + 1, a.length -1, x);
        }

    }

    private static int binarySearch (int[] a, int lb, int hb, int x) {
        assert a != null;

        if (lb > hb) return -1;

        int mid = (lb + hb)/2;

        if (a[mid] == x) return mid;

        if (a[mid] < x) {
            return binarySearch(a, mid + 1, hb, x);
        } else {
            return binarySearch(a, lb, mid - 1, x);
        }
    }

    /**
     * Returns the index of greatest element of the rotated sorted array.
     * if array is not rotated sorted, results are unprodictable
     * 
     * @param a     the input array
     * @param lb    the lower bound
     * @param hb    the higher bound
     * @return      the index of the highest element in the array.
     */
    private static int findPartition(int[] a, int lb, int hb) {
        assert a!= null;

        if (lb == hb) return -1;

        int mid = (lb + hb)/2;

        if (a[mid] > a[mid + 1]) {
            return mid;
        }

        if (a[mid] > a[hb]) {
            // go right.
            return findPartition(a, mid + 1, hb);
        } else {
            // go left.
            return findPartition(a, lb, mid); // note i cannot do mid - 1
        }
    }


    public static void main(String[] args) {
        // even length of the array.
        int[] a1 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected -1, Actual : " + binarySearchForRotatedArray(a1, -1));
        int[] a2 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected 1, Actual : " + binarySearchForRotatedArray(a2, 7));
        int[] a3 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected 5, Actual : " + binarySearchForRotatedArray(a3, 3));
        int[] a4 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected 2, Actual : " + binarySearchForRotatedArray(a4, 8));
        int[] a5 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected 3, Actual : " + binarySearchForRotatedArray(a5, 1));


        // odd length of the array. 
        int[] a6 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected -1, Actual : " + binarySearchForRotatedArray(a6, -1));
        int[] a7 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected 2, Actual : " + binarySearchForRotatedArray(a7, 7));
        int[] a8 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected 6, Actual : " + binarySearchForRotatedArray(a8, 3));
        int[] a9 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected 3, Actual : " + binarySearchForRotatedArray(a9, 8));
        int[] a10 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected 4, Actual : " + binarySearchForRotatedArray(a10, 1));
    }
}

Answer 1

As mentioned in my comment, the structure you are dealing with is more commonly called a circular buffer. The Wikipedia link has several examples on how to efficiently provide thread safe read/write access (a producer/consumer queue), but what's more important is the idea that you can abstract the access to your circular buffer to an interface, so that callers deal with it like it's an ordinary list.

The interface might look something like this (sorry for my poor Java skills):

public interface IReadonlyList<T>
{
    // gets the item at the specified index
    T getItem(int index);

    // gets the length
    int length();
}

And the circular buffer implementation would simply offset the internal index before returning the requested value:

// note that _headOffset and _actualArray aren't
// assigned anywhere, it's just a concept

public class CircularBuffer<T> : IReadonlyList<T>
{
    private final int _headOffset;
    private final T[] _actualArray;

    public T getItem(int index)
    {
        var actualIndex = (index + _headOffset) % Length;
        return _actualArray[actualIndex];
    }

    public int length()
    {
        return _actualArray.Length;
    }
}

Wrapping the class in an interface like this allows you to use a general binary search algorithm you would use for a standard sorted list (and any other algorithm which would work on a non-circular buffer).

Answer 2

Here's what I've done :

• enhanced the tests
• support sorted array (circular array with a shift of 0)
• remove recursion for optimisation and clearer signature

/**
 * This is utility class for operations on rotated one-d array.
 *
 * Complexity: O (log n)
 */
public final class RotatedOneDSortedArray {

    private RotatedOneDSortedArray() { }

    /**
     * Searches for the value provided in the rotated sorted array.
     * If found, returns the index, of provided array, else returns -1.
     * If array is not rotated and sorted, then results are unpredictable
     *
     * Throws an exception if array is null.
     *
     * @param a the rotated sorted array
     * @param x the element to be searched
     * @returns the index at which the element is found, else returns -1
     */
    public static int binarySearchForRotatedArray(int[] a, int x) {
        int partitionIndex = findPartition(a);

        if (partitionIndex == -1) return -1;

        if (x >= a[0] && x <= a[partitionIndex]) {
            return binarySearch(a, 0, partitionIndex, x);
        } else {
            return binarySearch(a, partitionIndex + 1, a.length -1, x);
        }

    }

    private static int binarySearch (int[] a, int lb, int hb, int x) {
        assert a != null;

        while (lb <= hb)
        {
            int mid = (lb + hb)/2;
            int midv = a[mid];
            if (midv < x) {
                lb = mid + 1;
            } else if (midv > x) {
                hb = mid -1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * Returns the index of greatest element of the rotated sorted array.
     * if array is not rotated sorted, results are unprodictable
     *
     * @param a     the input array
     * @return      the index of the highest element in the array.
     */
    private static int findPartition(int[] a) {
        assert a!= null;

        int lb = 0;
        int hb = a.length-1;

        // Check if rotation is 0
        if (a[lb] < a[hb])
            return hb;

        while (lb != hb)
        {
            int mid = (lb + hb)/2;

            if (a[mid] > a[mid + 1]) {
                return mid;
            } else if (a[mid] > a[hb]) {
                // go right.
                lb = mid + 1;
            } else {
                // go left.
                hb = mid; // note i cannot do mid - 1
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        // even length of the array.
        int expected = 0; int actual = 0;
        int[] a1 = {6, 7, 8, 1, 2, 3};
        expected = -1; actual = binarySearchForRotatedArray(a1, -1);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        int[] a2 = {6, 7, 8, 1, 2, 3};
        expected = 1; actual = binarySearchForRotatedArray(a2, 7);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        int[] a3 = {6, 7, 8, 1, 2, 3};
        expected = 5; actual = binarySearchForRotatedArray(a3, 3);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        int[] a4 = {6, 7, 8, 1, 2, 3};
        expected = 2; actual = binarySearchForRotatedArray(a4, 8);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        int[] a5 = {6, 7, 8, 1, 2, 3};
        expected = 3; actual = binarySearchForRotatedArray(a5, 1);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);

        // odd length of the array.
        int[] a6 = {4, 6, 7, 8, 1, 2, 3};
        expected = -1; actual = binarySearchForRotatedArray(a6, -1);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        int[] a7 = {4, 6, 7, 8, 1, 2, 3};
        expected = 2; actual = binarySearchForRotatedArray(a7, 7);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        int[] a8 = {4, 6, 7, 8, 1, 2, 3};
        expected = 6; actual = binarySearchForRotatedArray(a8, 3);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        int[] a9 = {4, 6, 7, 8, 1, 2, 3};
        expected = 3; actual = binarySearchForRotatedArray(a9, 8);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        int[] a10 = {4, 6, 7, 8, 1, 2, 3};
        expected = 4; actual = binarySearchForRotatedArray(a10, 1);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);

        // properly sorted
        int[] a11 = {1, 2, 3, 4, 5, 6, 7};
        expected = -1; actual = binarySearchForRotatedArray(a11, 0);
        expected = 0;  actual = binarySearchForRotatedArray(a11, 1);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        expected = 1;  actual = binarySearchForRotatedArray(a11, 2);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        expected = 2;  actual = binarySearchForRotatedArray(a11, 3);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        expected = 3;  actual = binarySearchForRotatedArray(a11, 4);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        expected = 4;  actual = binarySearchForRotatedArray(a11, 5);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        expected = 5;  actual = binarySearchForRotatedArray(a11, 6);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        expected = 6;  actual = binarySearchForRotatedArray(a11, 7);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);
        expected = -1; actual = binarySearchForRotatedArray(a11, 8);
        if (expected != actual) System.out.println("Expected " + expected + " , Actual : " + actual);

    }
}