desiredValue // искомое значениеint a[N]; // массив, где проводится поискint left = 0; // левая граница поискаint right = N; // правая граница поискаint middle; // среднее значениеwhile (left < right)
{
middle = left + (right - left) / 2;
if (a[middle] < desiredValue)
left = middle + 1;
else
right = middle;
}
if (a[right] == desiredValue)
return right;
else
return -1;
Я не до конца понимаю как работает этот алгоритм. У меня возникает множество вопросов почему.
Например:
1) Я хочу доказать, что результат работы при успешном поиске будет находится в right.
Суть работы алгоритма, в моём понимании, это разделить задачу на мелкие подзадачи
до тех пор пока не останется неделимая задача и тогда можно будет решить её. И... не соображаю дальше как это связать с кодом выше.
2) Доказать, что найденное значение является первым среди возможных одинаковых значений. Тут я смутно понимаю, что это как-то связано с тем, что массив наш отсортирован, но дальше не вижу куда двигаться.
3) Почему при a[middle] < desiredValue мы делаем left = middle + 1? Не получится ли так, что из-за такой границы мы не учтём один элемент? Так то я понимаю, что если не делать middle + 1, то мы никогда не выйдем из цикла. Но вот как выразить это присваивание словами?
У Кнута для лучшего понимания нарисовано двоичное дерево. Действительно, как я увидел тот рисунок двоичного дерева, у меня не возникают все эти вопросы почему, но сейчас то у меня простой массив и у меня сомнения, что двоичное дерево можно просто взять и наложить на массив.
Прошу помочь разобраться с этими вопросами. Я действительно не вижу как это работает.
Здравствуйте, 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>Прошу помочь разобраться с этими вопросами. Я действительно не вижу как это работает.
Здравствуйте, 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>Прошу помочь разобраться с этими вопросами. Я действительно не вижу как это работает.
Ответ не совсем по теме:
в таких случаях обычно поступаю просто — пишу юнит-тест из примерно десятка кейсов с разными входными данными.
Для данного случая: чётное-нечётное-нулевое число элементов, порядок по возрастанию-по убыванию, строгий-нестрогий.
Если все тесты отработали — считаю, что алгоритму в первом приближении можно доверять.
Прошу помочь понять верно ли я понял принцип математической индукции.
У нас есть сумма вида: 1 + 2 + 3 +...+ n. Я делаю предположение, что эта сумма вычисляется по формуле n^2. С помощью математической индукции я хочу проверить эту гипотезу.
База индукции. P(1): 1 = n^2 = 1^2. Значит, высказывание P(1) истинно.
Переход. P(n + 1):
Прибавим (n + 1) к обеим частям равенства 1 + 2 + 3 +...+ n = n^2.
1 + 2 + 3 +...+ n + (n + 1) = P(n) + P(n + 1) = n^2 + (n + 1)
Если же мы подставим (n + 1) вместо n в формулу n^2, то получим
(n + 1)^2 = n^2 + 2n + 1
Таким образом гипотеза, что сумма такого ряда чисел вычисляется по формуле n^2 ложна.
Я верно рассуждаю?
Здравствуйте, Stgl, Вы писали:
S>У Кнута для лучшего понимания нарисовано двоичное дерево. Действительно, как я увидел тот рисунок двоичного дерева, у меня не возникают все эти вопросы почему, но сейчас то у меня простой массив и у меня сомнения, что двоичное дерево можно просто взять и наложить на массив.
Двоичное дерево относится к подзадачам, а не к массиву. На каждом шаге в цикле решается, в какой половине отсортированного массива находится искомое, т.е. вместо начальной задачи решается задача половинного размера.
S>Прошу помочь разобраться с этими вопросами. Я действительно не вижу как это работает.
Забей на left. Смотри на right. Он всегда указывает на конец той половины, в которой ищем — т.е. то, что лежит в right, всегда больше или равно тому, что ищем. left постоянно подтягивается под начало этой половины. middle+1 потому что нет смысла дважды просматривать middle.
Здравствуйте, 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.
Вообще говоря, не будет, ибо не учтен случай, когда искомый элемент больше всех элементов массива. Пример a[] = {1}, ищем 2. Получаем обращение за границу массива.
S>Суть работы алгоритма, в моём понимании, это разделить задачу на мелкие подзадачи S>до тех пор пока не останется неделимая задача и тогда можно будет решить её. И... не соображаю дальше как это связать с кодом выше.
Не совсем. На каждом шаге алгоритм отсекает половину диапазона, в которой точно нет искомого значения.
S>2) Доказать, что найденное значение является первым среди возможных одинаковых значений. Тут я смутно понимаю, что это как-то связано с тем, что массив наш отсортирован, но дальше не вижу куда двигаться.
Это тривиально. Инвариантом алгоритма является то, что все, что левее left меньше искомого, а все, что правее right не меньше. Это верно и в конце, где left = right. То есть, левее могут быть только меньшие элементы.
S>3) Почему при a[middle] < desiredValue мы делаем left = middle + 1? Не получится ли так, что из-за такой границы мы не учтём один элемент? Так то я понимаю, что если не делать middle + 1, то мы никогда не выйдем из цикла. Но вот как выразить это присваивание словами?
Потому, что a[middle] заведомо меньше требуемого. Соответственно, нет смысла его оставлять в диапазоне поиска. Что-то не учесть мы не можем, ибо вне [left, right] точно нет того, что нам нужно.
Здравствуйте, Lexey, Вы писали:
L>Вообще говоря, не будет, ибо не учтен случай, когда искомый элемент больше всех элементов массива. Пример a[] = {1}, ищем 2. Получаем обращение за границу массива.
Таки да. right нужно инициализировать как N-1. Или проверять в конце, что оно не равно N.
Здравствуйте, Lexey, Вы писали:
S>>1) Я хочу доказать, что результат работы при успешном поиске будет находится в right. L>Вообще говоря, не будет, ибо не учтен случай, когда искомый элемент больше всех элементов массива. Пример a[] = {1}, ищем 2. Получаем обращение за границу массива.
Можно мысленно дописать a[N] = +oo и a[-1] = -oo
S>>3) Почему при a[middle] < desiredValue мы делаем left = middle + 1? Не получится ли так, что из-за такой границы мы не учтём один элемент? Так то я понимаю, что если не делать middle + 1, то мы никогда не выйдем из цикла. Но вот как выразить это присваивание словами?
L>Потому, что a[middle] заведомо меньше требуемого. Соответственно, нет смысла его оставлять в диапазоне поиска. Что-то не учесть мы не можем, ибо вне [left, right] точно нет того, что нам нужно.
Кстати, с интервалами у нас интересно вышло. Мы всё время имеем дело с закрытым интервалом [left,right]. То есть, мысленно допускаем наличие a[N].
И только специальные меры не позволяют нам выстрелить по памяти: номер точки разбиения округляется влево.
Впрочем, самая последняя проверка таки стреляет по памяти.
Здравствуйте, Stgl, Вы писали:
S>Прошу помочь разобраться с этими вопросами. Я действительно не вижу как это работает.
начнём с трисективного бин поиска.
desiredValue // искомое значениеint a[N]; // массив, где проводится поискint left = 0; // левая граница поиска int right = N; // правая граница поиска
// диапазон полуоткрытый [0,n)int middle; // место биекции/триекции while (left < right){
middle = left + (right - left) / 2;
if (desiredValue<a[middle])
right = middle - 1;
else if (desiredValue==a[middle])
return middle;
else//if(a[middle]<desiredValue)
left = middle + 1;
}
return right;
смотри лекции Степанова почему нужно не -1 и прочий NULL , а обыденную позицию. в данном случае например right вполне ( например когда искомое больше наибольшего в массиве будет возвращёна позиция за последним,)(например когда искомое меньше наименьшего в массиве будет возвращена позиция пред первым(это уже не по феншую ))
из вышеприведенного кода можно с целью пипхола сделать исходный вариант с двумя только ветками — путём слияние равенства с одним из крайних случаев и соответствующей(через рассуждения) модификацией ветвей
ps для красоты:
desiredValue // искомое значениеint a[N]; // массив, где проводится поискint left = 0; // левая граница поиска int right = N; // правая граница поиска
// диапазон полуоткрытый [0,n)int middle; // место биекции/триекции while(left < right){
switch(sign(desiredValue-a[middle = left + (right - left)/2]){
case -1:right = middle - 1;continue;
case 0:return middle;
case 1:left = middle + 1;continue;
}
}
return right;
pps. лучше писать чуть (не более чем в 2 раза) более медленный поиск в упорядоченном массиве, чем ошибочный быстрый.
ну а вообще реальным программистам бинарный поиск писать за карьеру редко кому надо
Перекуём баги на фичи!
