Массивы

На рис.1.1 показан массив из семи элементов с числовыми значениями. Чтобы найти в нем нужное нам число, мы можем использовать линейный поиск – его алгоритм приведен на рис. 1.2. Максимальное число сравнений при таком поиске – 7; оно достигается в случае, когда нужное нам значение находится в элементе A[6]. Если известно, что данные отсортированы, можно применить двоичный поиск (рис. 1.3). Переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы двое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Рис. 1.1: Массив

Двоичный поиск – очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй – до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Кроме поиска нам необходимо бывает вставлять и удалять элементы. К сожалению, массив плохо приспособлен для выполнения этих операций. Например, чтобы вставить число 18 в массив на рис. 1.1, нам понадобится сдвинуть элементы A[3]…A[6] вниз – лишь после этого мы сможем записать число 18 в элемент A[3]. Аналогичная проблема возникает при удалении элементов. Для повышения эффективности операций вставки/удаления предложены связанные списки.

int function SequentialSearch (Array A , int Lb , int Ub , int Key ); begin for i = Lb to Ub do if A ( i ) = Key then return i ; return –1; end;

Рис. 1.2: Линейный поиск

int function BinarySearch (Array A , int Lb , int Ub , int Key ); begin do forever M = ( Lb + Ub )/2; if ( Key < A[M]) then Ub = M – 1; else if (Key > A[M]) then Lb = M + 1; else return M ; if (Lb > Ub ) then return –1; end;

Рис. 1.3: Двоичный поиск

Предлагаю ознакомиться с аналогичными статьями: