Бинарный поиск (реализация на языке Java)

Java   3 апреля 2012  Автор статьи:  

Нижеприведенная функция binarySearch производит бинарный поиск элемента х в массиве array. В качестве результата выдается индекс вхождения элемента х или -1, если элемент х не имеет вхождения в массив.

public static > int binarySearch(List array, T x){
int l = 0;
int r = array.size()-1;
while(r-l>1){
int med = l+(r-l)/2;
if(array.get(med).compareTo(x)<0){ l = med; }else{ r = med; } } for(int i=l;i<=r;i++){ //нахождение элемнта х на интервале [l..r] if(array.get(i).equals(x)){ return i; } } return -1;

Нетрудно доказать, что данный код находит именно первое вхождение элемента х в массив array. Поэтому функция нахождения первого вхождения элемента х в массив аrray будет иметь вид:

public static > int firstIndexOf(List array, T x){
return binarySearch(array,x);
}

Аналогично можно найти и последнее вхождение элемента х в массив array, немного модифицировав исходный алгоритм:

public static > int lastIndexOf(List array, T x){
int l = 0;
int r = array.size()-1;
while(r-l>1){
int med = l+(r-l)/2;
if(array.get(med).compareTo(x)<1){//данное сравнение гарнтрует что l = med; //последнее вхождение всегда будет }else{ //на отрезке [l..r] r = med; } } for(int i=r;i>=l;i--){ //в этом случае мы идем в отрезке [l..r] справа налево
if(array.get(i).equals(x)){
return i;
}
}
return -1;
}

Следует также заметить, что в классе Collections стандартно реализованы вышеприведенные функции, имеющие примерно такой же принцип работы.

Научиться программировать

  • на Delphi

  • на Java

  • на C++