Короткая версия взламывая Collections.binarySearch
Каркас имеет built-in binary search и generic List<T> interface, вы должны использовать их.
Функция встроенного binarySearch всегда предоставляет элемент поворота компаратору в качестве второго аргумента.Это недокументированная поведение, но мы можем использовать это, используя следующий компаратор:
public static class FindLadderInterval implements Comparator<Ladder> {
public final int min, max;
public FindLadderInterval(int min, int max) {
this.min = min;
this.max = max;
}
@Override
public int compare(Ladder lhs, Ladder rhs) {
// ignore rhs
int length = lhs.length();
return length < this.min ? -1 : length > this.max ? 1 : 0;
}
}
Затем вы можете использовать его таким образом:
int index = Collections.binarySearch(list, null, new FindLadderInterval(12, 15));
Рабочий пример:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Main2 {
public static class Ladder {
private final int _length;
public Ladder(int length) {
this._length = length;
}
public int length() {
return this._length;
}
@Override
public String toString() {
return "Ladder(" + this._length + ")";
}
}
public static class FindLadderInterval implements Comparator<Ladder> {
public final int min, max;
public FindLadderInterval(int min, int max) {
this.min = min;
this.max = max;
}
@Override
public int compare(Ladder lhs, Ladder rhs) {
// ignore rhs
int length = lhs.length();
return length < this.min ? -1 : length > this.max ? 1 : 0;
}
}
public static void main(String[] args) {
List<Ladder> list = new ArrayList<Ladder>();
list.add(new Ladder(1));
list.add(new Ladder(2));
list.add(new Ladder(6));
list.add(new Ladder(13));
list.add(new Ladder(17));
list.add(new Ladder(21));
int index = Collections.binarySearch(list, null,
new FindLadderInterval(12, 15));
System.out.println("index: " + index);
System.out.println("ladder: " + list.get(index));
}
}
Длинная версия используя правильные алгоритмы
Ваша задача найти элемент в интервале - это не просто бит ary search, но мы можем реализовать его с помощью функции binarySearch, аналогичной встроенной, потому что это возвращает индекс вставки как отрицательное число, если элемент не был найден. Таким образом, мы можем искать элемент в конце интервала, если он найден, затем верните его, и если он не найден, просто проверьте, находится ли элемент в индексе вставки в интервале и возвращает его. Таким образом, алгоритм вернет последний элемент в интервале.
public static <T, R extends Comparable<? super R>> int intervalBinarySearchBy(
List<T> list, R min, R max, Function<? super T, ? extends R> selector) {
int idx = binarySearchBy(list, max, selector);
if (idx >= 0) return idx;
// Collections.binarySearch returns the insertion index binary
// negated if the element was not found
idx = ~idx;
return (idx < list.size()
&& min.compareTo(selector.apply(list.get(idx))) <= 0) ? idx : -1;
}
Чтобы использовать встроенный в Collections.binarySearch или вашей функции, вам необходимо предоставить представительный элемент, который довольно трудно, когда, например, вы упорядочивает строки от их длины. Чтобы найти строку длиной 15, вы должны указать строку длиной 15. Вот почему мне нравится стиль стиля python намного больше, в котором используются ключевые функции или селекторы. В принципе, вам не нужны сравнения, а сопоставление сопоставимых значений. Например, отображение от String до Integer, например s -> s.length(). Это дает возможность реализовать сладкие функции, как эти (лямбды сделать это довольно):
List<Person> list = getPersons();
Person youngest = minBy(list, p -> p.getAge());
Person tallest = maxBy(list, p -> p.getHeight());
Person person42 = findBy(list, 42, p -> p.getAge());
sortBy(list, p -> p.getAge());
Престолу, не нужно Comparator заказывать товары по недвижимости. Простая задача, простое решение. К сожалению, я не знаю таких функций как в стандартной библиотеке, так и в сторонних организациях. Но они могут быть реализованы.
рабочий пример в Java 8:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.function.Function;
public class Main {
public static class Collections2 {
/**
* Mimics Collections.binarySearch
*
* @param list
* @param pivotKey
* @param selector
* @return
*/
public static <T, R extends Comparable<? super R>> int binarySearchBy(
List<T> list, R pivotKey,
Function<? super T, ? extends R> selector) {
int low = 0;
int high = list.size() - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int ord = selector.apply(list.get(mid)).compareTo(pivotKey);
if (ord < 0) {
low = mid + 1;
} else if (ord > 0) {
high = mid - 1;
} else {
return mid;
}
}
return ~high; // bitwise negated insertion point /* -(a+1) == ~a */
}
/**
* Finds the index of the last element in the interval, or returns -1 if
* no such element was found.
*
* @param list
* @param min
* @param max
* @param selector
* @return
*/
public static <T, R extends Comparable<? super R>> int intervalBinarySearchBy(
List<T> list, R min, R max, Function<? super T, ? extends R> selector) {
int idx = binarySearchBy(list, max, selector);
if (idx >= 0) return idx;
// Collections.binarySearch returns the insertion index binary
// negated if the element was not found
idx = ~idx;
return (idx < list.size()
&& min.compareTo(selector.apply(list.get(idx))) <= 0) ? idx : -1;
}
public static <T, R extends Comparable<? super R> > Comparator<T> comparatorBy(
Function<? super T, ? extends R> selector) {
return (a, b) -> selector.apply(a).compareTo(selector.apply(b));
}
}
public static Function<Ladder, Integer> LENGTH_OF = a -> a.length();
public static class Ladder {
private final int _length;
public Ladder(int length) {
this._length = length;
}
public int length() {
return this._length;
}
@Override
public String toString() {
return "Ladder(" + this._length + ")";
}
}
public static void main(String[] args) {
List<Ladder> list = new ArrayList<Ladder>();
list.add(new Ladder(5));
list.add(new Ladder(9));
list.add(new Ladder(14));
list.add(new Ladder(7));
list.add(new Ladder(22));
list.add(new Ladder(23));
list.add(new Ladder(11));
list.add(new Ladder(9));
Collections.sort(list, Collections2.comparatorBy(LENGTH_OF));
int i = 0;
for (Ladder s : list) {
System.out.println("" + (i++) + ": " + s);
}
int foundIdx = Collections2.intervalBinarySearchBy(list, 12, 15,
LENGTH_OF);
System.out.println("Index: " + foundIdx);
System.out.println(list.get(foundIdx));
}
}
Любой метод поиска, который нужно будет найти что-то между '' Ā' и B' бы по самой своей природе должны знать, как '' Ā' и b', т.е. нижняя и верхняя границы. Ваш метод поиска принимает только 1 'x', так как вы можете сказать ему два числа' 12' и '15'? – Andreas
@ Андреас хорошо, вот где я боюсь. Я не вижу никакого способа сделать это. Я могу жестко закодировать его, так как я знаю положение лестницы, которое я ищу, но, видимо, что-то можно сделать в Functor, чтобы этого избежать. –
@SarahvdByl Я отредактировал свой ответ. – Saud