Здравствуйте, Stgl, Вы писали:
S>Есть нижеследующий алгоритм двоичного поиска.
S>S>desiredValue // искомое значение
S>int a[N]; // массив, где проводится поиск
S>int left = 0; // левая граница поиска
S>int right = N; // правая граница поиска
S>int middle; // среднее значение
S>while (left < right)
S>{
S> middle = left + (right - left) / 2;
S> if (a[middle] < desiredValue)
S> left = middle + 1;
S> else
S> right = middle;
S>}
S>if (a[right] == desiredValue)
S> return right;
S>else
S> return -1;
S>
S>Я не до конца понимаю как работает этот алгоритм. У меня возникает множество вопросов почему.
S>Например:
S>1) Я хочу доказать, что результат работы при успешном поиске будет находится в right.
S>Суть работы алгоритма, в моём понимании, это разделить задачу на мелкие подзадачи
S>до тех пор пока не останется неделимая задача и тогда можно будет решить её. И... не соображаю дальше как это связать с кодом выше.
S>2) Доказать, что найденное значение является первым среди возможных одинаковых значений. Тут я смутно понимаю, что это как-то связано с тем, что массив наш отсортирован, но дальше не вижу куда двигаться.
S>3) Почему при a[middle] < desiredValue мы делаем left = middle + 1? Не получится ли так, что из-за такой границы мы не учтём один элемент? Так то я понимаю, что если не делать middle + 1, то мы никогда не выйдем из цикла. Но вот как выразить это присваивание словами?
S>У Кнута для лучшего понимания нарисовано двоичное дерево. Действительно, как я увидел тот рисунок двоичного дерева, у меня не возникают все эти вопросы почему, но сейчас то у меня простой массив и у меня сомнения, что двоичное дерево можно просто взять и наложить на массив.
S>Прошу помочь разобраться с этими вопросами. Я действительно не вижу как это работает.
Исходить нужно из этого:
Инвариант цикла
