kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1757850118
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int
sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within
specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest
greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(
+ T[] array,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ return binarySearch0(array, 0, array.length, key, keyExtractor,
comparator);
+ }
+
+ /**
+ * Searches element in array sorted by key, within range fromIndex -
toIndex (inclusive - exclusive).
+ *
+ * @param array
+ * array sorted by key field
+ * @param fromIndex
+ * start index
+ * @param toIndex
+ * end index (exclusive)
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within
specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest
greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @throws ArrayIndexOutOfBoundsException
+ * when fromIndex or toIndex is out of array range
+ * @throws IllegalArgumentException
+ * when fromIndex is greater than toIndex
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <T, K> int binarySearch(
+ T[] array,
+ int fromIndex, int toIndex,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ if (fromIndex > toIndex) {
+ throw new IllegalArgumentException(
+ "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+ }
+ if (fromIndex < 0) {
+ throw new ArrayIndexOutOfBoundsException(fromIndex);
+ }
+ if (toIndex > array.length) {
+ throw new ArrayIndexOutOfBoundsException(toIndex);
+ }
+
+ return binarySearch0(array, fromIndex, toIndex, key, keyExtractor,
comparator);
+ }
+
+ // common implementation for binarySearch methods, with same semantics:
+ private static <T, K> int binarySearch0(
+ T[] array,
+ int fromIndex, int toIndex,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ int l = fromIndex;
+ int h = toIndex - 1;
+
+ while (l <= h) {
+ final int m = (l + h) >>> 1; // unsigned shift to avoid overflow
+ final K value = keyExtractor.apply(array[m]);
+ final int c = comparator.compare(value, key);
+ if (c < 0) {
+ l = m + 1;
+ } else if (c > 0) {
+ h = m - 1;
+ } else {
+ // 0, found
+ return m;
+ }
+ }
+
Review Comment:
Then `l` reaches `h+1` and exits the loop, returning `-toIndex - 1` as
documented.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
