Эффективная функция Java для получения идентификатора из упорядоченного массива

Question

В программе на Java у меня есть массив объектов.Каждый объект имеет поле, представляющее собой идентификационный номер, и все поля являются общедоступными (нет методов получения и установки).Массив упорядочен по номеру ID, который является целым числом.Я не хочу использовать цикл for или подобную технику для циклического прохождения каждого объекта, потому что массив может быть большим.Итак,

1. какой алгоритм поиска сделает это эффективно, и ...
2. есть удобный Java-метод, который будет выполнять этот поиск для меня, поэтому мне не нужно писатьэто сам?

Answer 1

Либо используйте java.util.Arrays.binarySearch () (если это массив примитивов или у вас есть Comparator), либо java.util.Collections.binarySearch () (если у вас есть коллекция не-массива собственного Comparable объект).

Звучит так, как будто Arrays.binarySearch лучше подошел бы к вашей проблеме. Напишите правильный java.util.Comparator, который понимает ваш порядок.

Answer 2

Какой алгоритм поиска

Двоичный поиск.

Есть ли функция для этого?

Да, binarySearch в java.util.Arrays

Единственный улов - вам нужно написать Comparator, который извлекает поле id.Что-то вроде, если бы у вас был класс

static class A {
    int id;

    A(int _id) { this.id = _id; }
}

, он мог бы выглядеть как

Comparator<A> idComp = new Comparator<A>() {
    public int compare(A a1, A a2) {
        return new Integer(a1.id).compareTo(a2.id);
    }

    public boolean equals(A a1, A a2) {
        return a1.id == a2.id;
    }
};

Answer 3

Один из способов сделать это - взять массив заказов и искать его как двоичное дерево.Начните с середины, если искомое число больше запрашиваемого, повторите в разделе 1/2 - 3/4 - 1, если оно меньше, повторите в разделе 0 - 1/4 - 1/2.

Сделайте это рекурсивным и возьмите подмножество массива.При первом вызове это будет весь массив, во втором - либо верхняя, либо нижняя половина идентификатора, а при третьем вызове это будет фактически одна четверть исходного ... и т.1003 *