Философия Java


Поиск в отсортированном массиве


Как только массив отсортирован, вы можете выполнить быстрый поиск определенного элемента, используя 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 на массив, управляемый в ручную.




Начало  Назад  Вперед