Поиск в массивах
Второй вариант неупорядоченного поиска
Программу первого варианта линейного поиска можно немного усовершенствовать вводом дополнительного элемента – барьера.
ПРОГРАММА prg27_430 //prg27_430 – программа на псевдоязыке линейного поиска в массиве (вариант 2). //Вход: mas[n] – неупорядоченная последовательность двоичных значений длиной ri+1 ; k – искомое значение //Выход: i – позиция в mas[n] (0<i<n-l), соответствующая найденному символу. ПЕРЕМЕННЫЕ INT_BYTE n: //длина mas[n] INT_BYTE mas[n+l]: //массив для поиска размерностью п+1 (О..п) INT BYTE k: //искомый элемент INT_WORD i=0 //индекс НАЧ_ПРОГ i: = 0: mas[n]: = k //установить барьер 52: ЕСЛИ (k==mas[i]) TO ПЕРЕЙТИ_НА _exit 1:-1+1: ПЕРЕЙТИ_НА s2 _exit: ЕСЛИ i>n TO ПЕРЕЙТИ_НА exit_error //вывести значение i по месту требования exit_error: //вывести сообщение об отсутствии элемента КОН_ПРОГ :prg27_430 – программа на ассемблере линейного поиска в массиве (вариант 2). .data : задаем массив mas db 50h. 08h. 52h. 06h. 90h. 17h. 89h. 27h. 65h. 42h. 15h. 51h. 61h.67h.76h.70h n=$-mas db Oh дополнительный элемент для барьера k db 15h .code xor si.si mov al,k mov mas[n].al:i: = 0: mas[n]: = k //установить барьер s2: cmpal.mas[si] ;ЕСЛИ k==mas[i] TO ПЕРЕЙТИ_НА _exit je ok inc si jmps2;i:-1+l: ПЕРЕЙТИ_НА s2 ok: emp si,n:ЕСЛИ i>n TO ПЕРЕЙТИ_НА exit_error je exit_error:вставить реакцию на удачный результат поиска jmp exit exit_error:;реакция на неудачный результат поиска
Упорядоченный поиск
На практике массивы элементов (записей) обычно определенным образом упорядочиваются. Это облегчает задачу поиска в них, так как появляется возможность формализации этого процесса. Записи в массиве в зависимости от значений ключевых полей могут быть упорядочены в числовом или лексикографическом порядке.
Двоичный поиск
Этот вид поиска (программа prg10_242.asm) предназначен для выполнения поиска в упорядоченном массиве (записей), содержащем N числовых ключей: kl < k2 < <-. <kN. Упорядоченный массив чисел 02h, 04h, 06h, 08h, 16h, 24h, 38h, 45h, 47h, 48h, 56h, 57h, 58h, 70h, 76h, 79h можно представить в виде двоичного дерева (Рис. 2.5).
Рис. 2.5. Представление массива в виде двоичного дерева