Двоичный поиск

Эффективность последовательного поиска

Пример программы

q:=nil;

p:=table;

while (p<> nil) do

begin

if p^.k = key then

begin

search = p ;

exit;

end;

q = p;

p = p^.nxt;

end;

New (s);

s^.k:= key

s^.r = rec

s^.nxt: = nil;

if q = nil then table = s

else q.^nxt = s;

search: = s;

exit

Достоинством списковой структуры является ускорен­ный алгоритм удаления или вставки элемента в список.

Время вставки или удаления не зависит от количества элементов, а в массиве каждая вставка или удаление требуют передвижения примерно половины элементов.

Эффективность любого поиска может оцениваться по количеству сравнений аргумента поиска С с ключами табли­цы данных. Чем меньше количество сравнений, тем эффек­тивнее алгоритм поиска.

Эффективность последовательного поиска в массиве:

С = 1 +п, С = (п + 1)/2.

Целью поиска является выполнение следующих процедур:

1. Найденную запись считать.

2. При отсутствии записи произвести ее вставку в таблицу.

3. Найденную запись удалить.

Первая процедура занимает для них одно время. Вторая и третья процедуры для списочной структуры более эффективна (т. к. у массивов надо сдвигать эле­менты).

Если k- число передвижений элементов в массиве, то k= (n + 1)/2.

При отсортированных данных может использоваться двоичный метод поиска.

При таком поиске используется метод "разделяй и властвуй". Сначала производится проверка среднего элемента. Если его ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины.

Если же нет, то делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет, найден требуемый элемент или не будет больше элементов для проверки.

Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 сначала делается проверка среднего элемента, которым является число 5.

Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел 1 2 3 4 5. Здесь средним элементом является 3. Это значение меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел 4 5. На следующем шаге нужный элемент будет найден.

При двоичном поиске число сравнений в худшем случае равно log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.

Рассматриваемую функцию, которая реализует двоичный поиск для символьных массивов, можно использовать для поиска любой произвольной структуры данных, изменив блок сравнения и определение типа данного "DataItem".