index of Most-right smallest element in sorted array

Question

I have a big sorted array, and i want to find the index of most right smallest element fast. O(logn)

For example

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11 12
VALUE: 5 5 5 5 5 5 5 5 6 8  9  9 10 ......... N

The answer is 7

My opinion is binary search but I have doubts

Andreas · Accepted Answer

Since input is sorted, a binary search will find solution in O(log n).

For the people who think it'll be O(n), because they think they have to do linear search to find boundary, you're not thinking it through.

To find boundary, you don't stop the binary search when finding index of target value. You keep performing the binary search until you look at adjacent indexes.

To illustrate (I'll leave coding as an exercise to interested parties):

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11 12
VALUE: 5 5 5 5 5 5 5 5 6 8  9  9 10

Find smallest value at index 0, so 5. Now search for 5 until boundary found, i.e. until adjacent indexes with value on left and higher value on right is found:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11 12
VALUE: 5 5 5 5 5 5 5 5 6 8  9  9 10
       |-----------|--------------|  Found 5, so search right
                   |-----|--------|  Found 8, so search left
                   |-|---|           Found 5, so search right
                     |-|-|           Found 6, so search left
                     |-|             Adjacent, so search complete

Boundary found between index 7 and 8, so last index of smallest value is: 7

This can be generalized to find first/last index of any target number, or to find last index of number smaller than target, or first index of number greater than target, whether target number actually exists in the input.

UPDATE

Because I like the relational search operations of NavigableSet and NavigableMap, I thought it could be fun to implement the Arrays.binarySearch(int[] a, int key) equivalent methods of ceiling(), floor(), higher(), and lower(), as well as first() and last() variants of get().

To only implement the main binary search logic once, I decided to use a functional interface / lambda expression to handle the compare logic. Cloning the code or using a boolean would likely perform better, but what the heck, I'm just having fun.

So, here are the 6 binary search methods for an int[], and the private method with the main search logic:

/**
 * Returns the least index in this array with value strictly equal to the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryFirst(int[] a, int key) {
    int idx = binaryCeiling(a, key);
    return (idx < 0 || a[idx] != key ? -1 : idx);
}

/**
 * Returns the greatest index in this array with value strictly equal to the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryLast(int[] a, int key) {
    int idx = binaryFloor(a, key);
    return (idx < 0 || a[idx] != key ? -1 : idx);
}

/**
 * Returns the greatest index in this array with value strictly less than the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryLower(int[] a, int key) {
    return binarySearch(a, x -> Integer.compare(x, key) < 0);
}

/**
 * Returns the greatest index in this array with value less than or equal to the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryFloor(int[] a, int key) {
    return binarySearch(a, x -> Integer.compare(x, key) <= 0);
}

/**
 * Returns the least index in this array with value greater than or equal to the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryCeiling(int[] a, int key) {
    int idx = binaryLower(a, key) + 1;
    return (idx == a.length ? -1 : idx);
}

/**
 * Returns the least index in this array with value strictly greater than the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryHigher(int[] a, int key) {
    int idx = binaryFloor(a, key) + 1;
    return (idx == a.length ? -1 : idx);
}

private static int minComp = Integer.MAX_VALUE; // For stats
private static int maxComp = Integer.MIN_VALUE; // For stats
private static int countComp = 0;               // For stats
private static int countSearch = 0;             // For stats

private static int binarySearch(int[] a, IntPredicate searchRight) {
    if (a.length == 0)
        return -1;
    int comp = 0; // For stats
    int first = 0, last = a.length - 1;
    while (first + 1 < last) {
        int mid = (first + last) / 2;
        comp++; // For stats
        if (searchRight.test(a[mid]))
            first = mid;
        else
            last = mid;
    }
    int result;
    if (first == last || first == 0) {
        comp++; // For stats
        result = (searchRight.test(a[first]) ? first : first - 1);
    } else if (last == a.length - 1) {
        comp++; // For stats
        result = (searchRight.test(a[last]) ? last : last - 1);
    } else {
        result = first;
    }
    minComp = Math.min(minComp, comp); // For stats
    maxComp = Math.max(maxComp, comp); // For stats
    countComp += comp;                 // For stats
    countSearch++;                     // For stats
    return result;
}

Since some people seem to have trouble accepting that complexity is O(log n), I added collection of statistics to the main search logic.

Here is test code, performing 36 tests of 9 values (n=9). The search of empty input is not counted for the statistics.

public static void main(String[] args) {
    System.out.println("  =      =      <      <=    >=      >");
    System.out.println("First  Last   Lower  Floor Ceiling Higher  Input");
    test();
    test(1,1,1,1,1,9,9,9,9,9);
    test(1,1,1,5,5,5,9,9,9,9);
    test(1,1,1,1,1,1,1,1,1,1);
    test(5,5,5,5,5,5,5,5,5,5);
    test(9,9,9,9,9,9,9,9,9,9);
    test(0,1,2,3,4,5,6,7,8,9);
    System.out.printf("%nStats: min=%d, max=%d, avg=%s%n",
                      minComp, maxComp, countComp / (double) countSearch);
}
private static void test(int... a) {
    System.out.printf("%3d%7d%7d%7d%7d%7d     %s%n",
                      binaryFirst(a, 5), binaryLast(a, 5), binaryLower(a, 5),
                      binaryFloor(a, 5), binaryCeiling(a, 5), binaryHigher(a, 5),
                      Arrays.toString(a));
}

Output, searching for value 5

  =      =      <      <=    >=      >
First  Last   Lower  Floor Ceiling Higher  Input
 -1     -1     -1     -1     -1     -1     []
 -1     -1      4      4      5      5     [1, 1, 1, 1, 1, 9, 9, 9, 9, 9]
  3      5      2      5      3      6     [1, 1, 1, 5, 5, 5, 9, 9, 9, 9]
 -1     -1      9      9     -1     -1     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  0      9     -1      9      0     -1     [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
 -1     -1     -1     -1      0      0     [9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
  5      5      4      5      5      6     [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Stats: min=3, max=5, avg=3.75

As can be seen, the average search performed 3.75 compares (log2(9) = 3.169925), with worst case of 5 compares to perform one search.

I also did 4 different arrays of 10000 values, totally 24 searches:

Stats: min=14, max=15, avg=14.375

Again, average of 14.375 compares for searching 10000 values (log2(10000) = 13.287712).

I think that adequately proves my assertion of O(log n) complexity of a search.

And for full solution to the question:

public static int indexOfMostRightSmallest(int[] a) {
    return binaryLast(a, a[0]);
}
public static void main(String[] args) {
    int[] a = { 5, 5, 5, 5, 5, 5, 5, 5, 6, 8, 9, 9, 10 };
    System.out.println(indexOfMostRightSmallest(a));
}

Output

7

Stats: min=4, max=4, avg=4.0

index of Most-right smallest element in sorted array

Answers (1)

Related Questions