Бинарный поиск

Question

Я здесь о запросе, с которым я сталкиваюсь.

Мне было интересно, как бы я занялся настольной проверкой следующего кода.

Набор данных

0 1  2 3  4   5  6  7   8   9  10  11   12  13  14 15

4 7 19 25 36 37 50 100 101 205 220 271 306 321 456 500 /* Numbers are a bit messed up */

Алгоритм binarySearch

SET found TO FALSE
SET bottom TO zero
SET top TO sizeOfList-1
WHILE ( NOT found AND bottom <= top )
    SET middle TO (bottom+top) DIV 2
    IF searchValue < list element middle THEN
        SET top TO middle-1
    ELSE
        IF searchValue > list element middle THEN
            SET bottom TO middle+1
        ELSE
            SET position TO middle
            SET found TO TRUE
        ENDIF
    ENDIF
ENDWHILE

IF NOT found THEN
    RETURN –1
ELSE
    RETURN position
ENDIF

Answer 1

Лучший способ сделать это - сначала составить таблицу с одним столбцом для каждой переменной (found, bottom, top и т. Д.). Затем, «будь» компьютером, пошагово проходи код своей программы по одной строке за раз (вероятно, лучше всего записывать каждый номер строки, который ты посещаешь для отслеживания), принимая условные переходы на основе значений в твоей таблице. Каждый раз, когда вы изменяете переменную, добавляйте в таблицу новую строку с обновленными значениями. В конце концов, вы должны прийти к выражению return, и тогда все готово.