Рекурсивный поиск в массивах

В главе 4 уже были изложены некоторые алгоритмы обработки одномерных массивов, однако их обсуждение можно считать не полным, без рассмотрения рекурсивных аналогов, в частности бинарного поиска и быстрой сортировки массивов.

Многие рекурсивные алгоритмы строятся по схеме «разделяй и властвуй», предполагающей наличие двух рекурсивных вызовов, каждый из которых работает приблизительно на половине входных данных. Это позволяет разделить задачу на независимые подзадачи того же типа. Часто использование подхода «разделяй и властвуй» обеспечивает более быстрые решения, чем итерационные алгоритмы.

В качестве примера рассмотрим задачу поиска максимального элемента в одномерном массиве. Итеративный вариант решения задачи был рассмотрен в главе 4. Рекурсивное решение типа «разделяй и властвуй» — еще один простой способ решения той же задачи.

Задача 6.4 Напишите рекурсивный метод поиска максимального элемента в целочисленном массиве.

Объяснение: рекурсивный метод будет проводить поиск максимального элемента в массиве a[] от индекса left (левая граница подмассива) до right (правая граница подмассива) включительно. В методе два рекурсивных вызовов, каждый из которых работает на половине заданного участка массива. Задача сводится к нахождению максимального из двух элементов, и решается путем их сравнения. Если в подмассиве один элемент, то он возвращается методом как максимальный. Дерево вызовов рекурсивного метода max () для массива a={5, 10, 12, 8} представлено на рис. 6.4.

В программе используется новый способ вывода массива на экран. В методе println () применен методtoString () класса java.util.Arrays, который преобразует массив в строку.

Алгоритм работы рекурсивного метода:

• 1. Если индекс left равен индексу right, то завершить поиск и вернуть значение максимального элемента a[left], иначе выполнить действия п.2−3.
• 2. Поделить анализируемый участок массива пополам. Вызвать метод поиска максимального значения для левого подмассива с границами left и (left+right)/2 и для правого подмассива с границами (left+right)/2+1 и right. Возвращаемыеметодами максимальные элементы для левого и правого участков исследуемого подмассива сохранить в дополнительных переменных temp1 и temp2 соответственно.
• 3. Вернуть максимальный из двух элементов temp1 и temp2.

public class Ex₆_4.

{.

static int max (int[] a).

{.

return max (a, 0, a. length-1); }.

static int max (int[] a, int left, int right).

{.

if (left==right) return a[left];

else {.

int temp1= max (a, left,(left+right)/2);

int temp2= max (a,(left+right)/2+1,right);

returnMath.max (temp1,temp2);}.

}.

public static void main (String[] args).

{.

int[] a = {5,0,-10,9,15,100,-12,3};

System.out.println (java.util.Arrays.toString (a));

System.out.println («Max="+max (a));

}}.

Результат:

[5, 0, -10, 9, 15, 100, -12, 3].

Max=100.

Еще один алгоритм, построенный по принципу «разделяй и властвуй» — это бинарный поиск в упорядоченном массиве, который также называется методом половинного деления. Идея алгоритма заключается в следующем: если массив упорядоченный, то половину его элементов после сравнения ключа (искомого значения) со средним элементом можно отбросить. Если значение ключа меньше среднего элемента массива, то искомый элемент может находиться только в левой части массива, к которой применяется этот же метод бинарного поиска, если — больше, метод вызывается для правой части массива. Таким образом, в методе будет два рекурсивных вызова.

Метод бинарного поиска работает значительно быстрее метода линейного поиска, рассмотренного в главе 4. Так, поиск в неотсортированных массивах занимает время, пропорциональное n, где n-количество элементов массива. При использовании метода бинарного поиска по отсортированным данным среднее время поиска будет пропорционально .

Задача 6.5 Напишите рекурсивный метод поиска в отсортированном целочисленном массиве

Объяснение: в программе используются следующие переменные: массив a[], left — индекс первого элемента (левая граница), right — индекс последнего элемента (правая граница), middle — индекс среднего элемента исследуемого участка массива, key — ключ поиска (искомый элемент). Метод возвращает индекс элемента, значение которого совпадает с ключом поиска. Если элемент не найден, возвращается -1. Условием завершения рекурсии является условие, при котором значение ключа совпадает со значением некоторого элемента массива, номер этого элемента возвращается. Если же индекс первого элемента исследуемого участка массива превышает индекс последнего элемента, то искомое значение в массиве отсутствует и возвращается -1.

Алгоритм работы рекурсивного метода:

• 1. Если индекс left больше индекса right, то завершить поиск и вернуть значение -1, иначе выполнить действия п.2−4.
• 2. Определить индекс среднего элемента: middle=(left+right)/2.
• 3. Сравнить ключ поиска со средним значением. Если они совпадают, то поиск завершен и возвращается индекс среднего элемента — middle, иначе определить подмассив в котором следует продолжить поиск. Перейти к п. 4.
• 4. Если ключ поиска меньше значения среднего элемента, вызвать рекурсивный метод бинарного поиска для левого подмассива с границами left и middle-1, иначе выполнить вызов метода бинарного поиска для правого подмассива с границами middle+1 и right.

public class Ex₆_5.

{.

static int binarySearch (int[] a, int left, int right, int key).

{.

if (left>right) return -1;

else.

{.

int middle=(left+right)/2;

if (key==a[middle]) return middle;

elseif (key

return binarySearch (a, left, middle-1, key);

else.

return binarySearch (a, middle+1, right, key);

}.

}.

public static void main (String[] args).

{.

int[] a = {5,0,-10,9,15,100,-12,3};

System.out.println (java.util.Arrays.toString (a));

System.out.printf («Search (9) index=%d», binarySearch (a, 0, a. length-1,9));

}.

}.

Результат:

[5, 0, -10, 9, 15, 100, -12, 3].

Search (9) index=3.