Java's equivalent to bisect in python

Question

Is there an equivalent in Java for Python's bisect module? With Python's bisect you can do array bisection with directions. For instance bisect.bisect_left does:

Locate the proper insertion point for item in list to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used.

I know I can do this manually with a binary search too, but I was wondering if there is already a library or collection doing this.

Codi

Answer 1

You have two options:

• java.util.Arrays.binarySearch on arrays
  • (with various overloads for different array types)
• java.util.Collections.binarySearch on List
  • (with Comparable and Comparator overloads).
  • Combine with List.subList(int fromIndex, int toIndex) to search portion of a list

Photic

Wow didn't know that Arrays package have a binarySearch implementation, is it fast then? – Codi

@systemsfault: one would think that it's acceptable. Unfortunately, there's no left and right variant in Java ("If the list/array contains multiple elements with the specified value, there is no guarantee which one will be found.") – Photic

java.util.Collections.binarySearch seems to be the more appropriate of the two since it has the insertion point behavior. – Salbu

I am a bit confused here. BinarySearch returns negative if the item is not found, this is not the same behavior as bisect at all. – Supinator

@SimoneZandara Take a look at this - geeksforgeeks.org/collections-binarysearch-java-examples. Alternatively, https://mcmap.net/q/295386/-java-list-sorting-is-there-a-way-to-keep-a-list-permantly-sorted-automatically-like-treemap shows how to consume the negative index (~index). – Foothold

Answer 2

To this date (Java 8), this is still missing, so you must still make your own. Here's mine:

public static int bisect_right(int[] A, int x) {
    return bisect_right(A, x, 0, A.length);
}

public static int bisect_right(int[] A, int x, int lo, int hi) {
    int N = A.length;
    if (N == 0) {
        return 0;
    }
    if (x < A[lo]) {
        return lo;
    }
    if (x > A[hi - 1]) {
        return hi;
    }
    for (;;) {
        if (lo + 1 == hi) {
            return lo + 1;
        }
        int mi = (hi + lo) / 2;
        if (x < A[mi]) {
            hi = mi;
        } else {
            lo = mi;
        }
    }
}

public static int bisect_left(int[] A, int x) {
    return bisect_left(A, x, 0, A.length);
}

public static int bisect_left(int[] A, int x, int lo, int hi) {
    int N = A.length;
    if (N == 0) {
        return 0;
    }
    if (x < A[lo]) {
        return lo;
    }
    if (x > A[hi - 1]) {
        return hi;
    }
    for (;;) {
        if (lo + 1 == hi) {
            return x == A[lo] ? lo : (lo + 1);
        }
        int mi = (hi + lo) / 2;
        if (x <= A[mi]) {
            hi = mi;
        } else {
            lo = mi;
        }
    }
}

Tested with (X being the class where I store static methods that I intend to reuse):

@Test
public void bisect_right() {
    System.out.println("bisect_rienter code hereght");
    int[] A = new int[]{0, 1, 2, 2, 2, 2, 3, 3, 5, 6};
    assertEquals(0, X.bisect_right(A, -1));
    assertEquals(1, X.bisect_right(A, 0));
    assertEquals(6, X.bisect_right(A, 2));
    assertEquals(8, X.bisect_right(A, 3));
    assertEquals(8, X.bisect_right(A, 4));
    assertEquals(9, X.bisect_right(A, 5));
    assertEquals(10, X.bisect_right(A, 6));
    assertEquals(10, X.bisect_right(A, 7));
}

@Test
public void bisect_left() {
    System.out.println("bisect_left");
    int[] A = new int[]{0, 1, 2, 2, 2, 2, 3, 3, 5, 6};
    assertEquals(0, X.bisect_left(A, -1));
    assertEquals(0, X.bisect_left(A, 0));
    assertEquals(2, X.bisect_left(A, 2));
    assertEquals(6, X.bisect_left(A, 3));
    assertEquals(8, X.bisect_left(A, 4));
    assertEquals(8, X.bisect_left(A, 5));
    assertEquals(9, X.bisect_left(A, 6));
    assertEquals(10, X.bisect_left(A, 7));
}

Otherwhere

Answer 3

Just for completeness, here's a little java function that turns the output from Arrays.binarySearch into something close to the output from bisect_left. I'm obviously missing things, but this does the job for the simple case.

public static int bisectLeft(double[] a, double key) {
    int idx = Math.min(a.length, Math.abs(Arrays.binarySearch(a, key)));
    while (idx > 0 && a[idx - 1] >= key) idx--;
    return idx;
}

Madiemadigan

This changes binary search from O(lg n) to O(n), defeating one of the main purposes of using it in the first place. – Kesterson

@Kesterson - Yes, this was just to illustrate the precise difference between Java's binary search and python's bisect_left, and this will be inefficient if there are a significant number of repetitions in the list. To restore O(lg n) performance in the worst case, you'd replace the while loop with, say, some sort of doubling search, but at that point you're rolling your own thing anyway. – Madiemadigan

Answer 4

Why not do a quick port of the tried and tested Python code itself? For example, here's a Java port for bisect_right:

public static int bisect_right(double[] A, double x) {
  return bisect_right(A, x, 0, A.length);
}

private static int bisect_right(double[] A, double x, int lo, int hi) {
  while (lo < hi) {
    int mid = (lo+hi)/2; 
    if (x < A[mid]) hi = mid; 
    else lo = mid+1;
  }
  return lo; 
}

Foothold

Answer 5

Based on the java.util.Arrays.binarySearch documentation

Here I use the example for a long[] array, but one can adapt the code to utilize any of the supported types.

int bisectRight(long[] arr, long key) {
    int index = Arrays.binarySearch(arr, key);
    return Math.abs(index + 1);
}

Note: Limitation on the java API, by the following sentence from javadoc:

If the array contains multiple elements with the specified value,
there is no guarantee which one will be found

Indeed, I've tested that with sorted array of distinct elements. My use-case was for range grouping, where arr an array of distinct timestamps that indicate the start time of an interval.

Lorrin

Answer 6

You need to define on your own, here's mine:

bisect.bisect_left

public static int bisectLeft(int[] nums, int target) {
    int i = 0;
    int j = nums.length - 1;
    while (i <= j) {
        int m = i + (j-i) / 2;
        if (nums[m] >= target) {
            j = m - 1;
        } else {
            i = m + 1;
        }
    }
    return i;
}

bisect.bisect_right

public static int bisectRight(int[] nums, int target) {
    int i = 0;
    int j = nums.length - 1;
    while (i <= j) {
        int m = i + (j-i) / 2;
        if (nums[m] <= target) {
            i = m + 1;
        } else {
            j = m - 1;
        }
    }
    return j+1;
}

Conterminous

Answer 7

Derived from @Profiterole's answer, here is a generalized variant that works with an int->boolean function instead of an array. It finds the first index where the predicate changes.

public class Bisect {

    /**
     * Look for the last index i in [min, max] such that f(i) is false.
     *
     * @param function monotonous function going from false to true in the [min, max] interval
     */
    public static int bisectLeft(Function<Integer, Boolean> function, int min, int max) {
        if (max == min) {
            return max;
        }
        if (function.apply(min)) {
            return min;
        }
        if (!function.apply(max)) {
            return max;
        }
        while (true) {
            if (min + 1 == max) {
                return min;
            }
            int middle = (max + min) / 2;
            if (function.apply(middle)) {
                max = middle;
            } else {
                min = middle;
            }
        }
    }

    /**
     * Look for the first index i in [min, max] such that f(i) is true.
     *
     * @param function monotonous function going from false to true in the [min, max] interval
     */
    public static int bisectRight(Function<Integer, Boolean> function, int min, int max) {
        if (max == min) {
            return max;
        }
        if (function.apply(min)) {
            return min;
        }
        if (!function.apply(max)) {
            return max;
        }
        while (true) {
            if (min + 1 == max) {
                return max;
            }
            int middle = (max + min) / 2;
            if (function.apply(middle)) {
                max = middle;
            } else {
                min = middle;
            }
        }
    }
}

For example, to find the insertion point in an array, the function compares the value inserted with the values of the array:

@Test
public void bisect_right() {
    int[] A = new int[]{0, 1, 2, 2, 2, 2, 3, 3, 5, 6};
    assertEquals(0, bisectRight(f(A, -1), 0, A.length));
    assertEquals(1, bisectRight(f(A, 0), 0, A.length));
    assertEquals(6, bisectRight(f(A, 2), 0, A.length));
    assertEquals(8, bisectRight(f(A, 3), 0, A.length));
    assertEquals(8, bisectRight(f(A, 4), 0, A.length));
    assertEquals(9, bisectRight(f(A, 5), 0, A.length));
    assertEquals(10, bisectRight(f(A, 6), 0, A.length));
    assertEquals(10, bisectRight(f(A, 7), 0, A.length));
}

public Function<Integer, Boolean> f(int[] A, int x) {
    return n -> (n >= A.length || A[n] > x);
}

Illogical