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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 public  static <T extends Comparable<T>> int binarySearch(List<T> 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 будет иметь вид:

1
2
3
 public  static <T extends Comparable<T>> int firstIndexOf(List<T> array, T x){
       return binarySearch(array,x);
    }

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 public  static <T extends Comparable<T>> int lastIndexOf(List<T> 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++