Картинки из квадратов \ Презентация \ Разблокировка роста Великого Китайского Дерева \

12.2.3. Разрыв шаблона:
третий том становится первым

Начало см. здесь здесь.
"Зубр" "Искусства программирования", Дональд Кнут, поместил сортировку и поиск в третий том своего многотомника, охарактеризовав такого рода алгоритмы как "нечисленные". Мои инсайты по И Цзину свидетельствуют, однако, что напротив, связанные с сортировкой и поиском вещи являются наиболее фундаментальными арифметическими вещами. И что по этой причине они должны быть помещены в самую основу систематического курса арифметики. В особенности, такого курса арифметики, который неразрывно и органично связан с Computer Science.
Чтобы сделать эти тезисы более понятными, давайте задумаемся, почему в контексте рассмотрения процедуры двоичного (или "бинарного") поиска естественным образом возникает понятие двоичного (или "бинарного") дерева? Это можно сделать на примере очень подробного рассмотрения процедуры двоичного поиска у Гудмана - Хидетниеми или же на примере рассмотрения процедуры бинарного поиска у самого Д. Кнута.
Также давайте задумаемся о том, почему процедура бинарного поиска особенно любит случай, когда число N записей, среди которых осуществляется поиск, равно 2n - 1 для некоторого натурального числа n (ну точно как в Китайском Дереве, где реализуется случай n = 3)? Любопытно отметить, что когда идея бинарного дерева поиска вновь осозналась спустя тысячелетия после И Цзина уже в современном Computer Science, то осозналась она сначала именно для случая N = 2n - 1 (этот факт особо отметил Дональд Кнут, "зубр" "Искусства программирования").