Комментарии 156
С бинарным поиском проблем не возникало. В свое время повозился с пирамидальной сортировкой и максимальным потоком.
Собственно, эта статья — описание типичнейших ошибок, которые могут допустить программисты при разработке и некоторые размышления о красоте коде, и попытках совместить красоту с корректностью алгоритма и его унифицированностью. Проблема в том, что не получается получить все вместе.
Так и надо было остановиться на 3 попытке, и не заниматься premature generalization, нет?
Мне вообще непонятен смысл 4 попытки в аглоритме, возвращающем значение, а не индекс.
Мне вообще непонятен смысл 4 попытки в аглоритме, возвращающем значение, а не индекс.
Хм? Возвращается индекс. Но первого из дублирующих элементов, а не первого, какой найдем. Только что проверил и для рекурсивного, и для итеративного прямым тестированием. вызов binarySearch_Array_Recursive_Wrapper(new int[] { 0,3,4,4,4,4,4,4,4,4,5 }, 4) выдает 2, т.е. 2-й элемент равен 4, раньше 4-к в массиве нет
Да, извиняюсь. В первых попытках было значение, в 4 проглядел
А есть ли в этом смысл — возвращать индекс именно первого из дублирующих элементов? Это специфика, которая мне в общем-то не пригодилась ни разу, даже для олимпиадных задач.
Если потом потребуется перебирать все элементы, большие или равные искомого — то первый из дублирующих это то, что нужно. Аналогично, если потребуется перебирать строго большие — надо искать последний. Такое, например, используется в одном из вариантов слияния двух массивов без дополнительной памяти.
Ровно по этой причине поиск возвращает любой из равных. А кроме него есть lower/upperBound.
Интересно, каким образом авторы функций Search, LowerBound и UpperBound обошлись без нарушения принципа DRY.
См. этот комментарий. Ну это для lowerBound/upperBound. А бин. поиск который возвращает любой из равных может возвращать первый из равных.
Ну пирамидальная ещё ладно. А вот БДП с их красивым удалением меня какое-то время в тупик ставили:)
За последние полгода пришлось собеседовать 5 человек на должность веб-разработчика в нашу студию.
Первое задание, на котором повалилось 4 человека: «Отсортируйте массив целых чисел по возрастанию. Метод сортировки любой. Язык программирования любой». Все вспомнили про пузырек, но:
Итого из 5 человек только 1 смог написать банальную сортировку пузырьком. А зарплатные ожидания у всех пятерых были огого!
Первое задание, на котором повалилось 4 человека: «Отсортируйте массив целых чисел по возрастанию. Метод сортировки любой. Язык программирования любой». Все вспомнили про пузырек, но:
- 1 пытался писать использую только 1 условие (без циклов)
- 2 пытались писать с использованием только 1 цикла и 1 условия (думаю все помнят что нужно 2 вложенных цикла и условие)
- 1 сделал 2 вложенных цикла, но условие не внутри, а снаружи.
Итого из 5 человек только 1 смог написать банальную сортировку пузырьком. А зарплатные ожидания у всех пятерых были огого!
А Вы публикуйте подобные работы. Для кого-то будет обучающим пособием(как не надо делать), а другим просто поднимет настроение…
А нефиг пузырьком сортировать. Надо прямым перебором с созданием нового массива! Только хардор!
Хотя к комментарию есть вопрос — как можно написать сортировку без использования циклов? В чем там была суть идеи?
С 1 циклом еще боле-менее понятно. Так можно извратиться, в целом то. По крайне мере в голову приходит вариант с нахождением минимального значения в каждой итерации цикла и условии на перехват окончания цикла
Хотя к комментарию есть вопрос — как можно написать сортировку без использования циклов? В чем там была суть идеи?
С 1 циклом еще боле-менее понятно. Так можно извратиться, в целом то. По крайне мере в голову приходит вариант с нахождением минимального значения в каждой итерации цикла и условии на перехват окончания цикла
Надо прямым перебором с созданием нового массива! Только хардор!
Если я вас правильно понял, то это отличная штука, при малом разбросе значений и большом количестве элементов :) O(n+m) вроде получается.
Подозреваю что первый сортировал 2 числа =о)
Вы совершенно правы, без циклов нельзя.
По факту очень многие начинающие программисты (а точнее те, кто не учил программирование а просто про него слышал) не понимают разницы между циклом и условием. Печально.
По факту очень многие начинающие программисты (а точнее те, кто не учил программирование а просто про него слышал) не понимают разницы между циклом и условием. Печально.
Рекурсивно :) В той же сортировке слиянием можно процедуру слияния описать через рекурсию и всё чудесно пишется без единого цикла.
Метод любой, язык любой.
Без циклов и условий
Dim arr() As Integer = {1, 2, 5, 6, 3, 8, 4, 9, 7}
Dim result = From b In arr Order By b
'результат: 1,2,3,4,5,6,7,8,9
Без циклов и условий
НЛО прилетело и опубликовало эту надпись здесь
вы что, хотите писать программы без ошибок?
Я что, многого хочу?
Программа, написанная с «обычной» ошибкой и отсутствие программы (или программа типа return random();) — идентичные ситуации. Программа же, которая имеет критичную ошибку в редких случаях — гораздо опаснее.
Иногда человек говорит «я умею писать реализации алгоритма XYZ», но по факту такая реализация с багфиксингом может занять 2 недели брутто. Другой же человек говорит «я не умею писать XYZ», но по факту с гуглением и чтением док напишет за неделю.
Собственно, как мне показалось, статья призвана показать бессмысленность заявлений типа «X знает алгоритм Y» в реальной жизни.
Иногда человек говорит «я умею писать реализации алгоритма XYZ», но по факту такая реализация с багфиксингом может занять 2 недели брутто. Другой же человек говорит «я не умею писать XYZ», но по факту с гуглением и чтением док напишет за неделю.
Собственно, как мне показалось, статья призвана показать бессмысленность заявлений типа «X знает алгоритм Y» в реальной жизни.
>> int mid = left + (right — left) / 2; — как то сложновато
int mid = size >> 1;
читается попроще
int mid = size >> 1;
читается попроще
Вы всегда используется отрицания в случае, когда элемент не найден и нужно возвратить номер элемента для вставки.
Но это неверно. Что будет в случае, когда нужно вернуть индекс 0? В таком случае будет неясно нашел ли Ваш алгоритм нужный элемент или выдал позицию, куда вставить текущий элемент.
Для этой цели гораздо лучше подходит операция ~.
return -(1 + left);Но это неверно. Что будет в случае, когда нужно вернуть индекс 0? В таком случае будет неясно нашел ли Ваш алгоритм нужный элемент или выдал позицию, куда вставить текущий элемент.
Для этой цели гораздо лучше подходит операция ~.
Если left = 0, тогда return — (1 + 0) = return -1. Все спец. индексы имеют отрицательное значение и смещение на 1.
Да, я понял, еще раз извиняюсь =)
Было дело писал интересную надстройку над классом List C# реализующий поиск первого и последнего элементав массиве при помощи бинарного поиска (например, в массиве 0 1 2 2 3 4 4 4 5 6 первый элемент равный 4 — 5, последний индекс элемента равного 4 — 7)
Простите, что код без комментариев и описания. Может кому-то пригодится. Возможно кто-то укажет что можно сделать лучше =)
using System;
using System.Collections.Generic;
using System.Text;
namespace ObfuscatedNamespace
{
public class List<T> : System.Collections.Generic.List<T>
{
public List() : base() {}
public List(IEnumerable<T> collection) : base(collection) { }
public List(int capacity) : base(capacity) { }
public int BinarySearchFirst(T item)
{
return BinarySearchFirst(0, Count, item, null);
}
public int BinarySearchFirst(T item, IComparer<T> comparer)
{
return BinarySearchFirst(0, Count, item, comparer);
}
public int BinarySearchFirst(int index, int count, T item, IComparer<T> comparer)
{
if (index < 0 || count < 0) throw new ArgumentOutOfRangeException();
if (index + count > Count) throw new ArgumentException();
if (comparer == null)
comparer = Comparer<T>.Default;
if (comparer == null) throw new InvalidOperationException();
int low = index;
if (count == 0)
return ~index;
int middle;
int len = count;
int half;
while (len > 0)
{
half = len / 2;
middle = low + half;
if (comparer.Compare(this[middle], item) < 0)
{
low = middle + 1;
len = len - half - 1;
}
else
len = half;
}
if (low >= count || comparer.Compare(this[low], item) != 0)
return ~low;
else
return low;
}
public int BinarySearchLast(int index, int count, T item, IComparer<T> comparer)
{
if (index < 0 || count < 0) throw new ArgumentOutOfRangeException();
if (index + count > Count) throw new ArgumentException();
if (comparer == null)
comparer = Comparer<T>.Default;
if (comparer == null) throw new InvalidOperationException();
int low = index;
if (count == 0)
return ~index;
int middle;
int r;
int len = count;
int half;
while (len > 0)
{
half = len / 2;
middle = low + half;
r = comparer.Compare(item, this[middle]);
if (r < 0)
len = half;
else
{
low = middle + 1;
len = len - half - 1;
}
}
if (low > 0)
{
r = comparer.Compare(item, this[low - 1]);
if (r == 0)
return low - 1;
else
return ~low;
}
else
return ~low;
}
public int BinarySearchLast(T item)
{
return BinarySearchLast(0, Count, item, null);
}
public int BinarySearchLast(T item, IComparer<T> comparer)
{
return BinarySearchLast(0, Count, item, comparer);
}
}
}
Простите, что код без комментариев и описания. Может кому-то пригодится. Возможно кто-то укажет что можно сделать лучше =)
Появился новый тег — <spoiler>. Загляните в подсказку к форме комментирования.
Интересный подход. Т.е. вы представляете область поиска через начальную точку и его длину?
Да, через начальную точку и длину. Такие же параметры принимает функция BinarySearch оригинального класса System.Collections.Generic.List (от которого я собственно и породил новый List).
Мне необходимо было пробегаться по определенной части массива элементов равных какому-то значению (например 4) причем в цикле и без операций сравнения на каждом шаге пробега (операции сравнения тяжеловесные, элементов в массиве много).
Мне необходимо было пробегаться по определенной части массива элементов равных какому-то значению (например 4) причем в цикле и без операций сравнения на каждом шаге пробега (операции сравнения тяжеловесные, элементов в массиве много).
Извиняюсь, не досмотрел сразу =) Но в любом случае, лучше пишите:
вместо
return ~left;
вместо
return -(1+left);
Век живи — век учись, сейчас добавлю апдейтом в пост.
Опасные это игрушки. В любом случае не помешает написать комментарий:
return ~left; // -(1+left); premature optimization
Чем строчку кода, которая поясняет строчку кода — лучше уж оставить старую версию…
Исходя из статьи я так и не понял, почему вы не можете написать бинарный поиск — вы его написали. И я бы не сказал, что путь был труден и тернист. Любая вещь сложнее 2 + 2 так и пишется. Сначала скелет, затем учёт нюансов и правка багов. Часть из последних может вылезти в дальнейшем. Их число будет меньше, если есть опыт в этой области, а мозг трезв :)
Что действительно вынесло мне мозг с корнями пару лет назад, так это динамика по изломанному профилю. Или мне не удалось найти внятного материала, или это страшно сложная штука.
Что действительно вынесло мне мозг с корнями пару лет назад, так это динамика по изломанному профилю. Или мне не удалось найти внятного материала, или это страшно сложная штука.
Ну это довольно желтый заголовок, но, вообще, я так и не понял, как правильно и красиво объединить бинарный поиск по массиву (целочисленные индексы) с бинарным поиском по функции (индексы с плавающей погрешностью, сама функция тоже с плавающей погрешностью). Ну и при этом хотелось получить некоего монстра, который может все, и выбирать первый элемент из дубликатов, и последний, и сам определять направление сортировки и при этом корректно работать на определенных интервалах.
прежде чем делать монстра, который делает все — сделайте монстра, который хорошо сделает то что нужно. Это одна из главных проблем — пытаться сразу все учесть.
А зачем Вам такой монстр? Хотите написать функцию «сделать хорошо»? Все таки алгоритмы должны быть под конкретную задачу, а не на все случаи жизни. Сегодня проскакивал опрос про то, сколько бесполезного кода пишет программист.
Не хватает юнит тестов.
Динамика по изломанному профилю — очень частная штука. Общая идея — сделаем профиль не прямым, а фигуристым. Из-за этого, естественно, меняется мощность профиля, функция переходов да и вообще логика. Но может получиться так, что общая асимптотика будет заметно лучше, чем при прямом профиле… Какая форма у фигуристого профиля и какие параметры этой формы — сильно зависит от задачи. В общем, штука не столько сложная, сколько очень частная и вполне можно было не найти внятного материала, ага…
Гугл, кстати, сходу выдает отличный пример: informatics.mccme.ru/moodle/mod/book/view.php?id=290&chapterid=78
Гугл, кстати, сходу выдает отличный пример: informatics.mccme.ru/moodle/mod/book/view.php?id=290&chapterid=78
Автор ищет красивый код, а функции именует, смешав все стили…
Да, по поводу именования. В оригинале (в исходном коде, который я писал) функции вообще назывались как binarySearch_Func_Recursive_Wrapper. Просто тут я придерживаюсь подхода, что если что-то в названии определяет способ действия или к чему прикладывается действие, то это нужно отделять несколько по другому. В реальности я бы написал private binarySearch() — собственно функция, и public binarySearch — функция-обертка.
int[] a = { 1, 3, 4, 6, 8, 4, 7, 8, 2, 3, 6, 1 };
Action<int, int> f = null;
f = delegate (int L, int R)
{
if (R - L == 1) return;
int pilot = a[L]; // (L+R)/2 заметно осложняет анализ. Если у нас есть предположение, что числа случайные, то никаких преимуществ одного перед другим нет.
int l = L, r = R;
// примем что для всех a[L..l) < pilot и a[r..R) >= pilot . Это условие должно выполняться на входе в цикл, по окончании каждой итерации, и на выходе из цикла.
// на каждой итерации должно происходить только одно из трёх: либо уменьшаться r , либо увеличиваться l, либо происходить обмен.
while (l != r) // только хардкор! никаких l <= r.
if (a[l] < pilot) l++;
else if (a[r-1] >= pilot) r--;
else
{
int t = a[l]; a[l] = a[r-1]; a[r-1] = t;
}
if (a[L] == pilot) // если pilot остался на своём месте, то pilot -- наименьший элемент во всём a[L,R). Просто пропускаем. Это тот самый случай вырождения в O(NN)
f(L + 1, R);
else
{ // помним, что после выхода из цикла l и r не менялись, следовательно, всё ещё l == r, все условия корректности выполняются
f(L, l);
f(r, R);
}
};
f(0, a.Length );
foreach(var e in a) System.Console.WriteLine(e);Извините, но то что у вас — это линейный поиск, кроме того, чрезвычайно запутанный. В статье же описывается бинарный поиск, для отсортированного массива. Он работает с асимптотикой O(lgn), т.е. время работы пропорционально логарифму n. Время работы линейного поиска пропорционально самому числу n (размеру массива).
Можно вызвать стандартную функцию: msdn.microsoft.com/en-us/library/w0k41tbs%28v=vs.71%29.aspx
Зачем так сложно-то?!
Функция, которая возвращает позицию элемента, значение которого равно х, в векторе v[], можно задать левую и правую границу поиска:
Функция, которая возвращает позицию элемента, значение которого равно х, в векторе v[], можно задать левую и правую границу поиска:
// Pre: (0 <= left) and (right < v.size()) and (v is sorted in an ascending order)
// Post: returns a number i, left<=i<=right and v[i]==x.
// If there is no element x in v[], returns -1.
int position(double x, const vector<double>& v, int left, int right) {
if (left > right) return -1;
int pos = (left + right)/2; // the middle of v[left,right]
if (x < v[pos]) return position(x, v, left, pos - 1);
if (x > v[pos]) return position(x, v, pos + 1, right);
return pos;
}
P.S. Используется алгоритм бинарного поиска, конечно же
Ваш метод теряет инфу (например, то, что вы возвращаете -1, а не ~left, не дает использовать функцию для поиска, куда нужно вставить определенный элемент), ваш метод работает только для одного направления сортировки, возвращает любой элемент, а не самый первый из дубликатов. Почитайте статью — куча кода написана не просто так.
А если сортировка была не по возрастанию или убыванию, а по отклонению от среднего элемента?
Ваш код этого тоже не предусматривает!
Хотите универсальности — смотрите на стандартные библиотеки. Считается, что элементы отсортированы по возрастанию в соответствии с переданной функцией сравнения. По умолчанию функция сравнения — оператор < для соответствующего типа.
Если пользователь отсортировал с одной функцией сравнения, а ищет с другой — то он сам себе злобный буратино.
Ваш код этого тоже не предусматривает!
Хотите универсальности — смотрите на стандартные библиотеки. Считается, что элементы отсортированы по возрастанию в соответствии с переданной функцией сравнения. По умолчанию функция сравнения — оператор < для соответствующего типа.
Если пользователь отсортировал с одной функцией сравнения, а ищет с другой — то он сам себе злобный буратино.
пыхпых
пардон, ctrl-enter случайно нажал. Продолжение коммента:
function bsearch($hs, $nee) {
$i1 = 0;
$i2 = count($hs);
do {
$i = floor(($i1 + $i2) / 2);
if ($hs[$i] == $nee) return $i;
if ($hs[$i] < $nee) $i1 = $i;
else $i2 = $i;
} while($i2 - $i1 > 1 || $i1 != $i);
return -1;
}
Еще вариант (немного компактнее + с учетом взятия минимального индекса из одинаковых и возврата ближайшего:
function bsearch_nearest($hs, $nee) {
for ($i1 = 0, $i2 = count($hs), $i = -1; $i2 - $i1 > 1 || $i1 != $i; ) {
$i = floor(($i1 + $i2) / 2);
if ($hs[$i] == $nee) return $i;
$hs[$i] < $nee? ($i1 = $i): ($i2 = $i);
}
return $i;
}
function bsearch($hs, $nee) {
$i = bsearch_nearest($hs, $nee);
while($i > 0 && $hs[$i - 1] == $nee) $i--; //return lowest index if there are few matching
return array(($hs[$i] == $nee? $i: -1), $i); //returns array: [0] => lowest matching index (or -1); [1] => nearest index
}
НЛО прилетело и опубликовало эту надпись здесь
Ну у нас печальный универ, как и вся страна впрочем :-)(. Украина, Харьков, ХИРЭ.
У нас будет предмет «Алгоритми та структури даних» на втором курсе, т.е. сразу после лета, но на ОДИН семестр. За гуманитарной и общеобразовательной ерунды у нас много. К примеру, у нас будет два семестра философии. Ну это если верить плану, который у нас кривой.
У нас будет предмет «Алгоритми та структури даних» на втором курсе, т.е. сразу после лета, но на ОДИН семестр. За гуманитарной и общеобразовательной ерунды у нас много. К примеру, у нас будет два семестра философии. Ну это если верить плану, который у нас кривой.
Насчёт возвращения первого/последнего из равных значений. В отсортированном массиве они всегда будут идти по порядку. Так почему бы не идти влево/вправо от найденного элемента, пока не наткнёмся на последнее равное значение:
if (type == last)
while (arr[n++] == value);
else
while (arr[n--] == value);
return n;
if (type == last)
while (arr[n++] == value);
else
while (arr[n--] == value);
return n;
Вот вам пример массива: 1 число 5, потом идет 10^9 чисел 8, потом идет число 9. Нужно найти первое вхождение числа 8. Прикиньте, сколько займет поиск
И тем самым вы переключаетесь с бинарного поиска в линейный!
А нужно всего лишь продолжать итерации бинарного поиска, но чуть поменять условие (искать не просто совпадение, а вдобавок НЕсовпадение предыдущего элемента).
А нужно всего лишь продолжать итерации бинарного поиска, но чуть поменять условие (искать не просто совпадение, а вдобавок НЕсовпадение предыдущего элемента).
Обычно, если функция может не увенчаться успехом, и нужно как-то уведомить об этом пользователя, а может, выкинуть исключение, то пишут 2 варианта функции:
static bool TryBinarySearch_Iter(int[] array, int key, out int index)
{
}
/// <exception cref=«KeyNotFoundException»/>
static int BinarySearch_Iter(int[] array, int key)
{
int result;
if (!TryBinarySearch_Iter(array, key, out result))
throw new KeyNotFoundException();
return result;
}
static bool TryBinarySearch_Iter(int[] array, int key, out int index)
{
}
/// <exception cref=«KeyNotFoundException»/>
static int BinarySearch_Iter(int[] array, int key)
{
int result;
if (!TryBinarySearch_Iter(array, key, out result))
throw new KeyNotFoundException();
return result;
}
Если вам интересно, как это обычно делают на олимпиадах про программированию.
1. Никому не надо искать первый элемент из одинаковых. Это упрощает алгоритм.
2. Направление убывания/возрастания известно в 90% случаев. А если не известно, то обычно все и еще хуже.
3. Рассматриваются 2 а не 3 случая.
Получается следующее:
Дальше тот, кто использует эту функцию может проверить найден x или отрезок [data[result], data[result+1]) которому он принадлежит сравнив data[result] и x. Ну и на него же ложатся обязанности проверить data[left]<=x, x<data[right]. Обычно используется left=0, right = data.length, а data[0]<=x следует из условия задачи. А если не следует, часто имеет смысл добавить фиктивный элемент.
Достоинства такого подхода — короче уже некуда и очень трудно в нем ошибиться. Достаточно понимать, что инвариант алгоритма это data[left]<=x<data[right]. Плюс можно использовать right=data.length, хотя такого элемента в массиве нет. Он предполагается равным +бесконечности.
1. Никому не надо искать первый элемент из одинаковых. Это упрощает алгоритм.
2. Направление убывания/возрастания известно в 90% случаев. А если не известно, то обычно все и еще хуже.
3. Рассматриваются 2 а не 3 случая.
Получается следующее:
int[] data;
int getIndex(int left, int right, int x) {
while (right-left>1) {
int middle=(left+right)/2; // обычно не нужно больше 10^9 элементов.
if (data[middle]>=x) {
left=middle;
} else {
right=middle;
}
}
return left;
}
Дальше тот, кто использует эту функцию может проверить найден x или отрезок [data[result], data[result+1]) которому он принадлежит сравнив data[result] и x. Ну и на него же ложатся обязанности проверить data[left]<=x, x<data[right]. Обычно используется left=0, right = data.length, а data[0]<=x следует из условия задачи. А если не следует, часто имеет смысл добавить фиктивный элемент.
Достоинства такого подхода — короче уже некуда и очень трудно в нем ошибиться. Достаточно понимать, что инвариант алгоритма это data[left]<=x<data[right]. Плюс можно использовать right=data.length, хотя такого элемента в массиве нет. Он предполагается равным +бесконечности.
> а что все-таки лучше — одна монструозная функция, которая поддерживает выбор первого/последнего/любого из них или три функции, чрезвычайно похожих, но немного не таких?
Лучше набор функций, каждая из которых делает одну простую задачу, но их можно комбинировать как кубики лего и создавать что-то более сложное. Такие функции проще читать и тестировать.
Как пример такого подхода здесь (с натяжкой):
* Чтобы найти последнее вхождение, можно перевернуть массив и искать первое.
* Поиск по массиву можно представить как поиск по функции. Функция в качестве Y возвращает элемент массива по индексу int(X). Если X меньше 0, или больше длины массива, тогда возвращаем минус бесконечность или бесконечность.
Но конечно лучше не морочить себе голову и написать 2 отдельных поиска, для массивов и функций. Тем более что для функций алгоритм будет очень отличаться, потому что начальные значения left и right могут быть неизвестны, и функция поиска сама должна их найти примерно таким способом. И вообще для монотонных функций лучше подходит метод секущих, он быстрее сходится.
Лучше набор функций, каждая из которых делает одну простую задачу, но их можно комбинировать как кубики лего и создавать что-то более сложное. Такие функции проще читать и тестировать.
Как пример такого подхода здесь (с натяжкой):
* Чтобы найти последнее вхождение, можно перевернуть массив и искать первое.
* Поиск по массиву можно представить как поиск по функции. Функция в качестве Y возвращает элемент массива по индексу int(X). Если X меньше 0, или больше длины массива, тогда возвращаем минус бесконечность или бесконечность.
Но конечно лучше не морочить себе голову и написать 2 отдельных поиска, для массивов и функций. Тем более что для функций алгоритм будет очень отличаться, потому что начальные значения left и right могут быть неизвестны, и функция поиска сама должна их найти примерно таким способом. И вообще для монотонных функций лучше подходит метод секущих, он быстрее сходится.
Переворачивание массива не пойдет по причине увеличения сложности алгоритма.
Не совсем понял, вычислительной сложности (big O), или сложности реализации bin_search?
Вот пример на Python как можно избежать и того и другого (хотя изврат еще тот):
Вот пример на Python как можно избежать и того и другого (хотя изврат еще тот):
from bisect import bisect_left
# our default binary search based on bisect_left() from stdlib
def bin_search_left(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
# reverse list in O(1): [1, 2, 3] -> [-3, -2, -1]
class RevList():
def __init__(self, list): self.list = list
def __len__(self): return len(self.list)
def __getitem__(self, key): return -self.list[len(self.list) - key - 1]
# rightmost occurrence in terms of bin_search_left
def bin_search_right(a, x):
return len(a) - 1 - bin_search_left(RevList(a), -x)
# and action!
arr = [2, 3, 5, 5, 5, 7, 11]
print bin_search_left(arr, 5) # 2
print bin_search_right(arr, 5) # 4
Спасибо за статью — очень понравилась! Примечательно, что большинство критиков приводят в пример намного худший код, если характеризовать его по признакам корректности, универсальности и читаемости.
А когда мне надо было написать, я взял у Кнута самый простой вариант и реализовал так (python):
Вывод:
# coding: utf-8
class Element:
def __init__(self, key, value):
self.key = key
self.value = value
def __str__(self):
return "%d (%s)" % (self.key, self.value)
# Обычный бинарный поиск
def BinSearch(arr, elem, l, u):
if not arr:
return -1
while True:
if u < l:
return -1
i = (l + u) / 2
if elem.key < arr[i].key:
u = i - 1
elif elem.key > arr[i].key:
l = i + 1
else:
return i
array = [Element(key, chr((key % 26) + 65,) ) for key in [1, 7, 11, 12, 24, 123]]
key = 12
print "array =", map(str, array)
print "key = %d" % key
print "index =", BinSearch(array, Element(key, "value"), 0, len(array) - 1)
raw_input("Press any key...")
Вывод:
array = ['1 (B)', '7 (H)', '11 (L)', '12 (M)', '24 (Y)', '123 (T)']
key = 12
index = 3
Press any key...
А почему нельзя использовать upper_bound и lower_bound? (кроме желания написать один алгоритм для решения всех задач, конечно) У них нет проблемы с тем, какой индекс вернуть. Они оставляют информацию о поиске, если используются для дальнейшей вставки элемента… Я что-то упускаю?
Мне прислали в личку решение с помощью операций lower_bound и upper_bound + объяснили их реализацию. Да, красиво.
По вашей просьбе размещаю и здесь:
осторожно, много текста
Давайте попробуем искать не первый/последний из эквивалентных элементов, а границы содержащего их интервала.
Интервал будет полуоткрытый справа, т.е. [lower_bound, upper_bound) как и все используемые интервалы. В случае, если искомого элемента нет, интервал будет пустой и обе границы (у пустого интервала границы равны) будут указывать на «место для вставки».
Для определения как отсортирована последовательность используем компаратор.
Будем считать, что компаратор comp в нашей последовательности выполняет роль оператора < и элементы в ней отсортированы по возрастанию (возрастанию относительно компаратора).
Т.е. если у нас последовательность целых чисел отсортирована по убыванию, то компаратором в ней будет оператор >. Если у нас последовательность пар чисел, отсортированных по величине второго числа… ну вы поняли о чем я.
lower_bound — позиция первого элемента, который не меньше искомого.
upper_bound — позиция первого элемента, который больше искомого.
Я буду использовать не индексы, а итераторы т.к. считаю, что в данной постановке задачи они уместнее (а ещё потому, что я это буду делать на C++ «в стиле STL»).
Попробуем найти lower_bound:
upper_bound можно выразить через lower_bound:
У нас есть оператор <, а нам нужен ≤.
Выразим одно через другое:
a ≤ b ⇔ !(b < a)
Варианты для компаратора по умолчанию пишутся тривиально.
Ну и осталась обертка для проверки входит ли элемент в последовательность и на какой позиции.
Последняя обертка, не даёт информацию о месте вставки, если элемент не нашелся, однако никто не запрещает воспользоваться lower_bound напрямую, если мы собираемся вставлять элемент.
За исключеним нескольких нюансов, мы практически переизобрели соответствующие алгоритмы из STL:
lower_bound
upper_bound
binary_search
equal_range
Тщательно не тестировал, но вроде работает.
Интервал будет полуоткрытый справа, т.е. [lower_bound, upper_bound) как и все используемые интервалы. В случае, если искомого элемента нет, интервал будет пустой и обе границы (у пустого интервала границы равны) будут указывать на «место для вставки».
Для определения как отсортирована последовательность используем компаратор.
Будем считать, что компаратор comp в нашей последовательности выполняет роль оператора < и элементы в ней отсортированы по возрастанию (возрастанию относительно компаратора).
Т.е. если у нас последовательность целых чисел отсортирована по убыванию, то компаратором в ней будет оператор >. Если у нас последовательность пар чисел, отсортированных по величине второго числа… ну вы поняли о чем я.
lower_bound — позиция первого элемента, который не меньше искомого.
upper_bound — позиция первого элемента, который больше искомого.
Я буду использовать не индексы, а итераторы т.к. считаю, что в данной постановке задачи они уместнее (а ещё потому, что я это буду делать на C++ «в стиле STL»).
Попробуем найти lower_bound:
template<typename FwdIter, typename T, typename Comp>
FwdIter lower_bound(FwdIter first, FwdIter last, T const& x, Comp comp)
{
// если интервал пустой, то его и возвращаем
if (first == last)
return first;
// вычислим позицию среднего элемента
FwdIter middle = first;
std::advance(middle, std::distance(first, last) / 2);
// Если средний элемент меньше искомого, т.е. искомый больше среднего элемента,
// то т.к. последовательность отсортирована по возрастанию,
// искомый элемент должен находиться справа от среднего, иначе — слева
if (comp(*middle, x))
return lower_bound(++middle, last, x, comp);
else
return lower_bound(first, middle, x, comp);
}
upper_bound можно выразить через lower_bound:
У нас есть оператор <, а нам нужен ≤.
Выразим одно через другое:
a ≤ b ⇔ !(b < a)
template<typename FwdIter, typename T, typename Comp>
FwdIter upper_bound(FwdIter first, FwdIter last, T const& x, Comp comp)
{
typedef typename std::iterator_traits<FwdIter>::value_type value_type;
auto less_equal = [&comp](value_type const& a, T const& b){return !comp(b, a);};
return lower_bound(first,last, x, less_equal);
}
Варианты для компаратора по умолчанию пишутся тривиально.
Ну и осталась обертка для проверки входит ли элемент в последовательность и на какой позиции.
template<typename FwdIter, typename T, typename Comp>
FwdIter binary_search(FwdIter first, FwdIter last, T const& x, Comp comp)
{
FwdIter found = lower_bound(first, last, x, comp);
// Если элемент не найден, found может оказаться равен правой границе.
// Если found указывает на существующий элемент, то он не меньше искомого.
// Т.е. *found или больше или равен x, если больше, то x не нашелся.
if (found == last || comp(x, *found))
{
// Элемент не найден.
// Вернем верхнюю границу диапазона в качестве индикатора.
return last;
}
return found;
}
Последняя обертка, не даёт информацию о месте вставки, если элемент не нашелся, однако никто не запрещает воспользоваться lower_bound напрямую, если мы собираемся вставлять элемент.
За исключеним нескольких нюансов, мы практически переизобрели соответствующие алгоритмы из STL:
lower_bound
upper_bound
binary_search
equal_range
Тщательно не тестировал, но вроде работает.
Капец. Столько комментариев, и до сих пор никто не дал простого совета: «попробуйте написать этот алгоритм через тесты». Каждый тест, по сути, и является записанным примером использования функции. Можно начинать с самых тривиальных примеров, чтобы создать интерфейс функции и базовый алгоритм работы, а затем, добавляя «неприятные» примеры один за другим, добиться корректной работы на граничных условиях.
Чистить код тоже намного проще, если он покрыт тестами. Надо просто прогонять их после каждого небольшого рефакторинга. Тогда сразу будет видно, что в логике ничего не сломалось.
Чистить код тоже намного проще, если он покрыт тестами. Надо просто прогонять их после каждого небольшого рефакторинга. Тогда сразу будет видно, что в логике ничего не сломалось.
Тесты наше все, если речь идет о примитивных алгоритмах вроде добавления лайка в базу. Но если задача не тривиальная, нужно сначала хорошо подумать и понять как ты ее будешь решать в принципе, а потом уже фигачить тесты.
Словами Питера Норвига:
«You can test all you want and if you don’t know how to approach the problem, you’re not going to get a solution.»
«Можно тестировать сколько угодно, но если ты не знаешь как подойти к проблеме, ты ничего этим не добьешься».
Вот классический пример (англ.) Один чувак (гуру тестирования), нафигачил тестов, но так как он тупо не знает как решить проблему в принципе, не сдвинулся с мертвой точки. Другой без всяких тестов сходу сел и написал красивейший код.
Словами Питера Норвига:
«You can test all you want and if you don’t know how to approach the problem, you’re not going to get a solution.»
«Можно тестировать сколько угодно, но если ты не знаешь как подойти к проблеме, ты ничего этим не добьешься».
Вот классический пример (англ.) Один чувак (гуру тестирования), нафигачил тестов, но так как он тупо не знает как решить проблему в принципе, не сдвинулся с мертвой точки. Другой без всяких тестов сходу сел и написал красивейший код.
Не понимаю, что Вы нашли нетривиального в алгоритме двоичного поиска. В списке кат, предназначенных для отработки навыков TDD, есть задачи куда сложнее.
Абсолютно тривиальный алгоритм. Но вот из Кнута: хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск не содержащий ошибок был опубликован только в 1962.
И в продолжение — ошибка в реализации из Java, которая оставалась незамеченной 10 лет. Умиляет апдейт 2008 года, когда они нашли еще одну ошибку.
И в продолжение — ошибка в реализации из Java, которая оставалась незамеченной 10 лет. Умиляет апдейт 2008 года, когда они нашли еще одну ошибку.
Так это ещё два аргумента в пользу использования TDD на этой задаче :)
В книге «Идеальный код» как раз есть статья Альберто Савойи «Красивые тесты», где разбирается тестирование (барабанная дробь...) двоичного поиска! В ней приводятся те же самые факты (Кнут & Бентли) в качестве аргументов к утверждению, что без тестов реализовать этот алгоритм правильно далеко не просто.
А далее подробно разбирается, как реализовать этот алгоритм, тестируя через JUnit. Найдите и почитайте статью. Рекомендую!
В книге «Идеальный код» как раз есть статья Альберто Савойи «Красивые тесты», где разбирается тестирование (барабанная дробь...) двоичного поиска! В ней приводятся те же самые факты (Кнут & Бентли) в качестве аргументов к утверждению, что без тестов реализовать этот алгоритм правильно далеко не просто.
А далее подробно разбирается, как реализовать этот алгоритм, тестируя через JUnit. Найдите и почитайте статью. Рекомендую!
По ссылке хорошие задачи, но тоже все тривиальные. Разве что в покере важно правильно выбрать представление рейтинга.
Всю статью не осилил.
Есть бинарный входящий в стандартный stl на плюсах:
binary seach
lower bound
Как я понимаю — нужно для обычных массивов, поэтому заменить итераторы на указатели, остальное вроде не сложно немного переделать.
Есть бинарный входящий в стандартный stl на плюсах:
binary seach
lower bound
Как я понимаю — нужно для обычных массивов, поэтому заменить итераторы на указатели, остальное вроде не сложно немного переделать.
Либо «Я некрофил и я недавно прочёл статью двухлетней давности», либо блог надо бы выбрать личный или Q&A.
Почему? Потому, что никаких выводов, никаких заключений. Морали — и той нету. Есть только вопрос «правильно ли я сваял функцию?»
Почему? Потому, что никаких выводов, никаких заключений. Морали — и той нету. Есть только вопрос «правильно ли я сваял функцию?»
Купите себе замечательную книгу Кормена «Алгоритмы: построение и анализ». Там всё достаточно внятно описано, очень советую.
Такие тривиальные вещи идеально «разгрызаются» через TDD. Задача не использует внешних ресурсов…. Эх, где мои 17 лет (читай 16-22)? Попробуйте и достигните нирваны.
Для целочисленного массива получилось так:
kf=-1 для первого элемента, 0 для любого, 1 для последнего.
Вроде бы, все учтено, поймать не удалось.
static int BinSearch(int[] m,int a,int kf) {
int len=m.Length;
int cf=0;
if(len==0) return -1;
if(m[0]>m[len-1]) {
a=~a; cf=-1;
}
int x1=-1,x2=len;
while(x2-x1>1) {
int x3=x1+(x2-x1)/2;
int h=m[x3]^cf;
if(h==a && kf==0) return x3;
if(kf<0 ? h>=a : h>a) x2=x3;
else x1=x3;
}
if(kf<0) {
if(x2<len && (m[x2]^cf)==a) return x2;
} else {
if(x1>=0 && (m[x1]^cf)==a) return x1;
}
return ~x2;
}
kf=-1 для первого элемента, 0 для любого, 1 для последнего.
Вроде бы, все учтено, поймать не удалось.
А с произвольным сравнением еще проще — 19 строк:
static int BinSearch(int[] m,int a,int kf,Comparison<int>cmp) {
int len=m.Length;
if(len==0) return -1;
int cf=cmp(m[0],m[len-1])<=0 ? 1 : -1;
int x1=-1,x2=len;
while(x2-x1>1) {
int x3=x1+(x2-x1)/2;
int h=cf*cmp(m[x3],a);
if(h==0 && kf==0) return x3;
if(kf<0 ? h>=0 : h>0) x2=x3;
else x1=x3;
}
if(kf<0) {
if(x2<len && cmp(m[x2],a)==0) return x2;
} else {
if(x1>=0 && cmp(m[x1],a)==0) return x1;
}
return ~x2;
}
а если все \r\n удалить?
Тогда будет неудобно читать.
Так уже. Вы же целеноправленно строки сокращаете :):
1. «thin return» на одной строке
2. Несколько переменных объявлено вместе
3. «kf<0? h>=0: h>0» — конфета
4. А где пробелы между логическими блоками? Я бы поставил минимум в трех местах.
1. «thin return» на одной строке
2. Несколько переменных объявлено вместе
3. «kf<0? h>=0: h>0» — конфета
4. А где пробелы между логическими блоками? Я бы поставил минимум в трех местах.
Ну, не знаю. Я так привык. В каждой строчке по одному оператору. Все строки достаточно короткие.
Возражения про «kf<0? h>=0: h>0» не понял вообще — нормальное условие, как мне кажется. «Пробелы между логическими блоками» — что имеется в виду?
Возражения про «kf<0? h>=0: h>0» не понял вообще — нормальное условие, как мне кажется. «Пробелы между логическими блоками» — что имеется в виду?
Я имел ввиду пустые строки отделяющие логические блоки кода. Здесь я бы поставил перед while, последним внешним if и return.
«kf<0? h>=0: h>0» не уверен :), но помоему он определяет в какую сторону идти в зависимости от направления отсортированности масива-параметра. Вобщем, без поллитра…
Может я и не прав, и вы код не уплотняли. Возможно, дело вкуса. Возможно, виноваты имена переменных. Но читать очень тяжело. Как результат — закрались сомнения :).
«kf<0? h>=0: h>0» не уверен :), но помоему он определяет в какую сторону идти в зависимости от направления отсортированности масива-параметра. Вобщем, без поллитра…
Может я и не прав, и вы код не уплотняли. Возможно, дело вкуса. Возможно, виноваты имена переменных. Но читать очень тяжело. Как результат — закрались сомнения :).
Нет, условие «kf<0? h>=0: h>0» определяет, какой конец отрезка из элементов, равных искомому, мы ищем — левый или правый. Направление отсортированности находится в переменной cf и используется в строчке «int h=cf*cmp(m[x3],a);»
А если бы я уплотнял строки, то:
— описал бы все три переменных x1,x2,cf в одной строке (нехорошо, поскольку в одну инициализацию попадают переменные разной семантической окраски. С x1, x2 такой проблемы нет — они оба индексы в массиве);
— поставил бы фигурные скобки в конец предыдущих строк (выигрыш 2 или 3 строк, но я так не люблю читать);
— поставил бы последний if сразу после else и убрал фигурные скобки. По моим критериям, в этом нет никакого криминала, но нарушается симметрия фрагмента программы.
А если бы я уплотнял строки, то:
— описал бы все три переменных x1,x2,cf в одной строке (нехорошо, поскольку в одну инициализацию попадают переменные разной семантической окраски. С x1, x2 такой проблемы нет — они оба индексы в массиве);
— поставил бы фигурные скобки в конец предыдущих строк (выигрыш 2 или 3 строк, но я так не люблю читать);
— поставил бы последний if сразу после else и убрал фигурные скобки. По моим критериям, в этом нет никакого криминала, но нарушается симметрия фрагмента программы.
Вообще у вас все варианты какие-то странные. Я вот в упор не понимаю, зачем вносить проверку на равенство в цикл, достаточно одной проверки на неравенство в цикле и одной проверки — вне его, это будет значительно эффективнее. Когда ковырял двоичный поиск под CUDA, написал следующее:
Хотя, это тоже специфика, CUDA «не любит» лишние ветвления.
На hashlist[2*x] не обращайте особого внимания, просто разбил 64-битные числа на 2 по 32 бита (так быстрее, но сравнивать нужно каждую «половинку»).
Скрытый текст
unsigned int left = 0, right = hashlist_count;
// now binary search
while (left < right)
{
unsigned int middle = left + (right - left) / 2;
if (a < hashlist[2*middle] ||
a == hashlist[2*middle] && b <= hashlist[2*middle+1])
{
right = middle;
}
else
{
left = middle + 1;
}
}
if (a == hashlist[2*right] && b == hashlist[2*right+1])
{
// matched!
unsigned int add = 1 << (output_index % 32);
atomicAdd(&(((unsigned int*)match_out)[output_index / 32]), add);
}
Хотя, это тоже специфика, CUDA «не любит» лишние ветвления.
На hashlist[2*x] не обращайте особого внимания, просто разбил 64-битные числа на 2 по 32 бита (так быстрее, но сравнивать нужно каждую «половинку»).
Да, пардон, с кодом погорячился:
В моем примере мы ищем пару (a:b) в массиве вида hashlist[2*n], отсюда такие хитрые условия. Не будь этого было бы достаточно (ищем x):
В моем примере мы ищем пару (a:b) в массиве вида hashlist[2*n], отсюда такие хитрые условия. Не будь этого было бы достаточно (ищем x):
unsigned int left = 0, right = hashlist_count;
// now binary search
while (left < right)
{
unsigned int middle = left + (right - left) / 2;
if (x < hashlist[middle])
{
right = middle;
}
else
{
left = middle + 1;
}
}
if (x == hashlist[right])
{
// matched!
}
Раз такое уже пошло, то и я свой код кину ))
Поломайте мозги.
Я для усложнения поставил себе задание — не использовать никакие ветвления и логические функции. На шарпе. Вот что получилось:
Конечно, я не показываю пример, как надо писать на шарпе. Надеюсь, кому-то станет интересно почитать такой функционально-матричный подход.
Поломайте мозги.
Я для усложнения поставил себе задание — не использовать никакие ветвления и логические функции. На шарпе. Вот что получилось:
static int BinarySearch(List<int> list, int num, Tuple<int, int> range)
{
int midleIndex = (range.Item1 + range.Item2) / 2;
Func<int>[,] funcs = new Func<int>[,]
{
{
() => -1, () => -1, () => -1
},
{
() => BinarySearch(list, num, new Tuple<int, int>(range.Item1, midleIndex)),
() => midleIndex,
() => BinarySearch(list, num, new Tuple<int, int>(midleIndex + 1, range.Item2))
}
};
return funcs[(1 + Math.Sign(1 + 2 * (list.Count - range.Item2))) * Math.Sign(range.Item2 - range.Item1) / 2, Math.Sign(num - list[midleIndex]) + 1]();
}
Конечно, я не показываю пример, как надо писать на шарпе. Надеюсь, кому-то станет интересно почитать такой функционально-матричный подход.
Красивый вариант :)
Но над чем тут ломать мозги? Все очевидно. Даже ошибку искать долго не пришлось: если при вычислении num — list[midleIndex] случится переполнение (например, num>2^30, list[midleIndex]<-2^30), то результат Sign будет неправильным.
И говорить, что вызов функции из массива не является использованием ветвления, по-моему, не совсем честно…
Но над чем тут ломать мозги? Все очевидно. Даже ошибку искать долго не пришлось: если при вычислении num — list[midleIndex] случится переполнение (например, num>2^30, list[midleIndex]<-2^30), то результат Sign будет неправильным.
И говорить, что вызов функции из массива не является использованием ветвления, по-моему, не совсем честно…
Код я не серьезно писал )
Понятно, что можно добавлять 0.5, все в дабл конвертнется, а знак брать тогда тоже можно. И код даже проще будет. Но как-то не хотелось даблами пользоваться. Прихоть такая.
Внутри сайна есть ветвление и тоже это не очень чисто. А вот пользоваться массивом вместо ветвления и не называть его ветвлением — вполне честно. Понятно, что вызов такой его моделирует. Даже свич можно смоделировать. Но свич или иф — это структура кода, а здесь структура данных. Куда и функции примешались.
Наверное можно еще что-то сделать такое, что упростит этот код. С ходу не придумал.
Понятно, что можно добавлять 0.5, все в дабл конвертнется, а знак брать тогда тоже можно. И код даже проще будет. Но как-то не хотелось даблами пользоваться. Прихоть такая.
Внутри сайна есть ветвление и тоже это не очень чисто. А вот пользоваться массивом вместо ветвления и не называть его ветвлением — вполне честно. Понятно, что вызов такой его моделирует. Даже свич можно смоделировать. Но свич или иф — это структура кода, а здесь структура данных. Куда и функции примешались.
Наверное можно еще что-то сделать такое, что упростит этот код. С ходу не придумал.
Понятно. Тут нужна двухуровневая схема — сначала отсеять пустые диапазоны, а уже потом сравнивать элемент с границами и с серединой. Код не упростится, но может стать надежнее.
Про ветвление внутри Sign — тоже вызов. Сейчас подумаю :)
Про ветвление внутри Sign — тоже вызов. Сейчас подумаю :)
Да, можно.
mov ebx,eax
neg ebx
or ebx,eax
sar ebx,31
sar eax,31
add eax,eax
inc eax
and eax,ebx
ret
Как-то так:
Не проверялось…
int BinSearch(int[] arr,int val){
return BinSearch(arr,val,-1,arr.Length);
}
int BinSearch(int[] arr,int val,int left,int right){
return (new Func<int>[]{()=>~right,()=>BinSearchNE(arr,val,left,right)})[Math.Min(right-left-1,1)]();
}
int BinSearchNE(int[] arr,int val,int left,int right){
int mid=left+(right-left)/2;
return (new Func<int>[]{
()=>BinSearch(arr,val,left,mid),
()=>mid,
()=>BinSearch(arr,val,mid,right))
}[Math.Sign((long)val-arr[mid])+1]();
}
Не проверялось…
И, кстати, если искомый элемент больше последнего элемента списка — не получится ли midleIndex==list.Count? Выход индекса за границу может случиться…
А зачем Math.Sign(1 + 2 * (list.Count — range.Item2))? Для защиты от некорректного входа? Ведь если в начале было 0<=range.Item1<=range.Item2<=list.Count, то оно так и останется. Или нет?
А зачем Math.Sign(1 + 2 * (list.Count — range.Item2))? Для защиты от некорректного входа? Ведь если в начале было 0<=range.Item1<=range.Item2<=list.Count, то оно так и останется. Или нет?
О, то бага! ))
Вначале я до запятой, первый параметр массива написал так:
Convert.ToInt32(range.Item2 <= list.Count && range.Item1 < range.Item2)
Т.е. как раз условие, чтобы не вышли за пределы массива. И смоделировал потом сайнами. Но наверное конец рабочего дня, где-то ошибся. Точнее я смоделировал это условие так, как надо (надеюсь, не проверял только что), но то ли у меня четное (или нечетное) число элементов было, что проходил код. Решается эта бага замечательно. Вот в этой строчке надо так:
int midleIndex = (range.Item1 + range.Item2 — 1) / 2;
Если учитываем, что левая часть всегда не включается, то приводим рейджу с настоящими элементами.
Но кажется, я перемудрил. Если сделать поправку со средним индексом, то достаточно сделать такое условие:
Convert.ToInt32(range.Item1 < range.Item2)
прошу прощения за ошибки, если даже сейчас ошибаюсь. Все таки после рабочего дня немного не так соображается. Финальная версия, надеюсь верная:
как-то работает
Вначале я до запятой, первый параметр массива написал так:
Convert.ToInt32(range.Item2 <= list.Count && range.Item1 < range.Item2)
Т.е. как раз условие, чтобы не вышли за пределы массива. И смоделировал потом сайнами. Но наверное конец рабочего дня, где-то ошибся. Точнее я смоделировал это условие так, как надо (надеюсь, не проверял только что), но то ли у меня четное (или нечетное) число элементов было, что проходил код. Решается эта бага замечательно. Вот в этой строчке надо так:
int midleIndex = (range.Item1 + range.Item2 — 1) / 2;
Если учитываем, что левая часть всегда не включается, то приводим рейджу с настоящими элементами.
Но кажется, я перемудрил. Если сделать поправку со средним индексом, то достаточно сделать такое условие:
Convert.ToInt32(range.Item1 < range.Item2)
прошу прощения за ошибки, если даже сейчас ошибаюсь. Все таки после рабочего дня немного не так соображается. Финальная версия, надеюсь верная:
static int BinarySearch(List<int> list, int num, Tuple<int, int> range)
{
int midleIndex = (range.Item1 + range.Item2 - 1) / 2;
Func<int>[,] funcs = new Func<int>[,]
{
{
() => -1, () => -1, () => -1
},
{
() => BinarySearch(list, num, new Tuple<int, int>(range.Item1, midleIndex)),
() => midleIndex,
() => BinarySearch(list, num, new Tuple<int, int>(midleIndex + 1, range.Item2))
}
};
return funcs[Math.Sign(range.Item2 - range.Item1), Math.Sign(num - list[midleIndex]) + 1]();
}
как-то работает
А мне понравился призыв автора написать свой поиск перед чтением топика. :)
Вот что получилось в стиле STL для std::vector (собирать компилятором с поддержкой C++11):
Поиск с возвратом любого попавшегося элемента: bs::find<тип, false>(где, что).
Поиск с возвратом первого элемента из последовательности одинаковых: bs::find<тип, true>(где, что). Поиск первого элемента — тоже двоичный, а не последовательный.
В обоих вариантах от типа E требуется только один оператор сравнения — меньше (<).
Вот что получилось в стиле STL для std::vector (собирать компилятором с поддержкой C++11):
Поиск с возвратом любого попавшегося элемента: bs::find<тип, false>(где, что).
Поиск с возвратом первого элемента из последовательности одинаковых: bs::find<тип, true>(где, что). Поиск первого элемента — тоже двоичный, а не последовательный.
В обоих вариантах от типа E требуется только один оператор сравнения — меньше (<).
#include <vector>
#include <iterator>
#include <iostream>
namespace bs {
namespace impl {
template<typename E, bool find_first>
typename std::vector<E>::const_iterator find(const std::vector<E>& where, const E& what, const typename std::vector<E>::const_iterator& begin, const typename std::vector<E>::const_iterator& end)
{
typename std::vector<E>::const_iterator::difference_type size = std::distance(begin, end);
if (size == 0)
return where.end();
typename std::vector<E>::const_iterator center = begin + size / 2;
if (what < *center)
return find<E, find_first>(where, what, begin, center);
if (*center < what)
return find<E, find_first>(where, what, center+1, end);
if (find_first) {
typename std::vector<E>::const_iterator leftmost = find<E, find_first>(where, what, begin, center);
if (leftmost != where.end())
return leftmost;
}
return center;
}
};
template<typename E, bool find_first>
typename std::vector<E>::const_iterator find(const std::vector<E>& where, const E& what)
{
return impl::find<E, find_first>(where, what, where.begin(), where.end());
}
};
int main(int argc, char* argv[])
{
std::vector<int> input = { 10, 21, 34, 34, 34, 35, 41, 45, 49, 67, 102, 120, 120, 120, 120, 120, 120, 201 };
std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl << std::endl;
int what;
for(;;) {
std::cout << "Find what: ";
std::cin >> what;
typename std::vector<int>::const_iterator found = bs::find<int, true>(input, what);
if (found == input.end()) {
std::cout << "Not found" << std::endl;
continue;
}
std::cout << "Found at " << std::distance(static_cast<std::vector<int>::const_iterator>(input.begin()), found) << std::endl;
}
return 0;
}
Вы неверно употребляете понятие «интервал». В контексте множеств чисел то, что вы называете интервалом, правильно называется отрезком.
Разница между множествами: в множество чисел отрезка включаются ограничивающие его величины, а в множество интервала — как раз наоборот.
Записываются соотверственно:
Разница между множествами: в множество чисел отрезка включаются ограничивающие его величины, а в множество интервала — как раз наоборот.
Записываются соотверственно:
- (left; right) — интервал;
- [left; right] — отрезок.
Скажите мне что вы курили, чтобы я этого никогда не пробовал.
Ну раз попросили написать перед прочтением, теперь хочется это «творчество» куда-то деть, беглым взглядом на правильные решения я понял, что мой вариант видимо немного избыточен, тем не менее пусть будет как есть. Заработало не с первого раза, но сложностей не было.
«спасибо» разработчикам хабра, видимо из-за недостатка дрочециферок теги source не работают
pastie.org/4128677
«спасибо» разработчикам хабра, видимо из-за недостатка дрочециферок теги source не работают
pastie.org/4128677
Зачем такой геморрой с порядком, в котором отсортирован массив? Вы пишете на C#? Используйте компаратор! Ну и выделять отдельный случай для mid = x совсем не обязательно. Просто сузим полуинтервал до размера 1 и проверим, равен ли его начальный элемент, искомому (Нередко, кстати, интересен наибольший, не превосходящий x). Заодно упростится поиск первого/последнего подходящего
Почему бы не рассматривать это как часть условия задачи — массив отсортирован в соответствии с компаратором, но заранее неизвестно, в прямом или обратном порядке. Если брать задачу в полном виде (3 режима поиска+2 возможных порядка) она становится достаточно интересной, чтобы заняться решением.
Вообще да, от меня идея юзать компараторы почему-то сразу же ускользнула. А по поводу сужения полуинтервала до размера 1 — как именно вы будете сужать полуинтервал, если вам нужно первый/последний из дублирующих? Ведь когда мы сужаем, мы выбрасываем средний элемент
как раз таки средний выбрасывать не надо: если он не превосходит х — сделаем его левым концом
Окей, допустим у нас массив из двух элементов: {20, 30}. Какой следующий шаг? Ведь полуинтервал не сократится, он так и останется [0, 2)
(0+2)/2 = 1
т.е. дальше останется либо полуинтервал [0,1) либо [1,2)
т.е. дальше останется либо полуинтервал [0,1) либо [1,2)
Смотрите, средний элемент — 1-й. Но поскольку мы его не выбрасываем, то у нас промежуток не меняется. Т.е. база рекурсии получается равна массиву из двух элементов, нет?
как раз таки средний выбрасывать не надо: если он не превосходит х — сделаем его левым концом
Я понял — вы включаете средний элемент, только в одном случае, если сокращение интервала уходит в правую половину. Т.е. [0, 2) разбивается или на [0, 1) (средний не включен) или на [1, 2) (средний включен).
Т.е. этот код будет искать последний элемент из дублирующих:
if (array[middle] <= x)
left = middle; // include middle
else
right = middle; // exclude middle
А этот код будет искать первый элемент из дублирующих:
if (array[middle] < x)
left = middle + 1; // exclude middle
else
right = middle + 1; // include middle
Но при этом эти коды мало того, что разные интервалы генерируют, в первом сравнение <=, а второе — просто <.
Такой вариант будет именно, что находить всегда последний.
Если надо первый, то меняем полуинтервал [) на (]
Если надо первый, то меняем полуинтервал [) на (]
Как-то это неправильно, менять тип полуинтервала
ну это мысленно меняем. а по факту — это просто выбор начальных значений и того, куда можно присоединить среднее значение
Почему неправильно? Это всего лишь условие проверки: определяем мы значение, равное заданному, как большее, чем надо, или как меньшее. У меня в коде, в сущности, так и делается:
habrahabr.ru/post/146228/#comment_4922036
В случае поиска первого элемента мы поддерживаем условие arr[left]<val<=arr[right] и в качестве ответа выдаем конечное значение right, если в нем находится val, а для поиска последнего — arr[left]<=val<arr[right], и ответом будет left. Если же значение не совпало с искомым, в обоих случаях выдается ~right.
habrahabr.ru/post/146228/#comment_4922036
В случае поиска первого элемента мы поддерживаем условие arr[left]<val<=arr[right] и в качестве ответа выдаем конечное значение right, если в нем находится val, а для поиска последнего — arr[left]<=val<arr[right], и ответом будет left. Если же значение не совпало с искомым, в обоих случаях выдается ~right.
Там всего 6 переменных. Переименуйте x1 в left, x2 — в right, а x3 — в middle. Думаете, станет понятнее? Понятного названия для переменной h, я, к сожалению, предложить не могу. В переводе на русский оно звучало бы примерно как «относительное расположение искомого элемента и элемента массива с индексов middle с учетом заданной операции сравнения, полученного порядка упорядоченния массива и возможного равенства этих двух элементов».
Написал на Питоне за 20 минут. Случаи с числом элментов равным 0, 1 или 2 обрабатывал вручную.
Рискну предположить, что вы не читали статью Как же все-таки правильно написать двоичный поиск?
Прошуршал все комментарии и странно что никто не заметил(а возможно что-то я накрутил).
Имеем в массиве 1 (200000) элемент с индексом 0.
Пытаемся найти элемент со значение 300000(left 0 right 1) и предполагаемое место вставки получаем -2. Хотя должны получить 0.
Это начиная со второй попытки.
Имеем в массиве 1 (200000) элемент с индексом 0.
Пытаемся найти элемент со значение 300000(left 0 right 1) и предполагаемое место вставки получаем -2. Хотя должны получить 0.
Это начиная со второй попытки.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Я не могу написать бинарный поиск