Поиск в отсортированном массиве
Как только массив отсортирован, вы можете выполнить быстрый поиск определенного элемента, используя Arrays.binarySearch( ). Однако очень важно, чтобы вы не пробовали использовать binarySearch( ) для не отсортированного массива, иначе получите непредсказуемый результат. Следующий пример использует RandIntGenerator для заполнения массива, затем для получения значений поиска:
//: c09:ArraySearching.java
// Использование Arrays.binarySearch().
import com.bruceeckel.util.*; import java.util.*;
public class ArraySearching { public static void main(String[] args) { int[] a = new int[100]; Arrays2.RandIntGenerator gen = new Arrays2.RandIntGenerator(1000); Arrays2.fill(a, gen); Arrays.sort(a); Arrays2.print("Sorted array: ", a); while(true) { int r = gen.next(); int location = Arrays.binarySearch(a, r); if(location >= 0) { System.out.println("Location of " + r + " is " + location + ", a[" + location + "] = " + a[location]); break; // выход из цикла
} } } } ///:~
В цикле while генерируются случайные значения в качестве элементов поиска до тех пор, пока одно из них не будет найдено.
Arrays.binarySearch( ) производит значение большее или равное нулю, если элемент найден. В противном случае он производит отрицательное значение, представляющее место, в котором этот элемент должен быть вставлен, если вы имеете дело с отсортированным массивом. Производимое значение - это
-(точка вставки) - 1
Точка вставки - это индекс первого элемента, который больше ключевого значения, или a.size( ), если все элементы массива меньше, чем указанное значение.
Если массив содержит дублирующиеся элементы, то нет гарантии, какой из них будет найден. Алгоритм реально не предназначен для поддержки поиска одинаковых элементов, если они допускаются. Однако, если вам нужен отсортированный список не дублируемых элементов, используйте TreeSet, который будет введен позже в этой главе. Он заботится обо всех деталях автоматически. Только в случае узкого места производительности вы должны заменить TreeSet на массив, управляемый в ручную.
Если у вас есть отсортированный массив объектов с использованием Comparator (массивы примитивных типов не позволяют выполнять сортировку с использованием Comparator), вы должны включить этот же самый Comparator, когда выполняете binarySearch( ) (используя перегруженную версию прилагаемой функции). Например, программа AlphabeticSorting.java может быть модифицирована для выполнения поиска:
//: c09:AlphabeticSearch.java
// Поиск с использованием Comparator.
import com.bruceeckel.util.*; import java.util.*;
public class AlphabeticSearch { public static void main(String[] args) { String[] sa = new String[30]; Arrays2.fill(sa, new Arrays2.RandStringGenerator(5)); AlphabeticComparator comp = new AlphabeticComparator(); Arrays.sort(sa, comp); int index = Arrays.binarySearch(sa, sa[10], comp); System.out.println("Index = " + index); } } ///:~
Comparator должен передаваться в перегруженный метод binarySearch( ) в качестве третьего аргумента. В приведенном выше примере успех гарантирован, потому что ищется элемент, выдернутый из массива.
