Обсуждение:Двоичный поиск

Неточность: Если проверка n==0 в начале опущена Невозможно пропустить только одну проверку, так как в этом операторе далее условие a[n - 1]<x т.е. будет a[-1] При удалении первого if, если x больше последнего элемента в массиве или n=0, после цикла last=first=n и n!=0 недостаточно для корректного условия 37.140.120.18 15:43, 16 октября 2012 (UTC) AD

* Что будет, если first и last по отдельности умещаются в свой тип, а first+last — нет?

4-байтный integer - это больше 2млрд. Вы часто видели массивы такой длинны?

Да элементарно. --Abeshenkov 07:23, 14 марта 2011 (UTC)

А конкретный пример? 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

Из того, что можно сделать дома легко и не принужденно - кэш для быстрой индексации файлов. А если посмотреть на спец софт, а уж тем при мат расчетах - бегом и живо. При тяжелых задачах встает обратный вопрос

При программировании под 32х битной WindowsNT размер доступного адресного пространства для процесса пользователя 2^31 байт (не считая редко используемого режима 3Gb). В unsigned int помещается 2^32 значений (а зачем использовать знаковые переменные если они не будут принимать отрицательные значения?). К тому же размер элементов массива такой длины врядли будет 1 байт. Если элементы имеют тип int (4 байта), то максимальное значение индексов будет не более 2^29, что уже гарантированно не даст переполнения. Если же массив действительно может быть больше 2 Гб (например дисковый), то его и адресовать нужно 64 битными переменными.

Зато mid = first + (last-first)/2 по сравнению с (first+last)/2 требует лишнюю операцию. В цикле. Клёво! 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

Операция сложения - по сравнению с операцией деления - нуль.

Операция сложения - это операция. Ваш К.О. А то, что она в цикле - это logN дополнительных операций. 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

Еще раз повторюсь, что скорость операции сложения порядка на два меньше деления. А уже тем более целочисленного

А каким образом этот код: first + (last-first)/2 позволяет экономить операцию деления? Никаким! Зато вводит дополнительное сложение. Ваш К.О. Используйте тогда уж побитовый сдвиг >>1 вместо /2. А для того, чтобы обойти переполнение int - достаточно завести long long mid. Но я Вам скажу по секрету, что если Вы всё же считаете звёзды и у Вас ВНЕЗАПНО получился массив на 1 миллиард, то не за горами и 2.5 миллиарда. Используйте long long для индексации.

ИМХО, если стоит выбор - пожертвовать 4 байтами памяти или производительностью - стоит пожертвовать 4 байтами памяти. 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

* Будет ли работать на пустом массиве (n=0)?

А вы пробовали создать массив нулевой длинны?

int a[0];

Си с такой конструкцией Вас пошлёт благим матом, ибо нефиг! 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

А вы не знаете про динамические массивы?

А бывают динамические массивы 0-й длинны? :-D 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

Имя массива - есть ссылка на ячейку, в которой лежит 0-й элемент. Ну, допустим... int *a; - это нифига не массив до тех пор, пока не будет выполнена malloc ;) 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

Видать контейнеры типа list вам неизвестны.--Abeshenkov 13:30, 14 марта 2011 (UTC)

Это был Си, а не С++. В любом случае list - это объект, а не массив! Давайте еще пару объектов придумаем, у которых будет еще пару индивидуальных особых случаев и всё это впихнём в код на Википедию... 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

Не следует смешивать понятия объёма памяти выделенного под массив и количества действительных элементов в нем. Можно, например, создать массив под максимально возможное количество элементов и отдельно переменную n, равную числу элементов помещенных в массив. Все ячейки массива расположенные дальше n-1 ячейки будут считаться недействительными и поиск в них производиться не должен. Начальное состояние такого массива как раз и будет соответствовать случаю n=0.

* Способен ли код находить отсутствующие значения? У некоторых программистов написанный «с листа» двоичный поиск в такой ситуации зацикливается — и они этого не осознают, пока тестирование не даст ошибку.

А слабо потестировать, а уже потом задавать этот вопрос? 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

Ну как видно, до ошибки с переполнением счетчика вы бы не дошли.--Abeshenkov 13:30, 14 марта 2011 (UTC)

Программисты пишут код из головы. Те, кто пишут код "с листа" - говнокодеры, которые не способны даже понять, что там написано! 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

/* Эти проверки можно опустить без ущерба для работоспособности кода */

Да неужели? Если эти проверки опустить, то благодаря этому:

size_t last = n; /* Элемент в массиве, СЛЕДУЮЩИЙ ЗА последним */

Произойдёт выход за пределы массива в этом месте:

if (/*n!=0 &&*/ a[last] == x) {

М-да, автор, написавший этот код этого не заметил.--Abeshenkov 13:30, 14 марта 2011 (UTC)

Нафига нужен СЛЕДУЮЩИЙ ЗА последним? Прекрасно будет работать и с последним!

Ну и рабочий (и протестированный) вариант:

int bSearch(int a[], int len, int target) {
    int left = 0;
    int right = len - 1;
    
    for ( ; left < right; ) {
        int mid = ( left + right ) / 2; // Объявите его как long long, если Вас так беспокоит переполнение int (нет, ну где Вы видели массив на миллиард элементов???)
        
        if ( a[mid] >= target ) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    if ( a[right] == target ) {
        return right;
    } else {
        return -1;
    }
}

Кто-то говорил про говнокод, а используете более тяжеловестный for, да с нарушенной логикой использования.--Abeshenkov 07:23, 14 марта 2011 (UTC)

while - это кастрированный for! Если ты уверен в обратном - обоснуй! 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

Вот поэтому он быстрее и выполняется.--Abeshenkov 13:30, 14 марта 2011 (UTC

То, что в иницииализации управляющей конструкции for опущены некоторые параметры - вовсе не говорит о нарушении логики его использования, ибо синтаксис это допускает ;)

ИМХО, компилятор и ту и другую конструкцию преобразует в одинаковый машинный код. Так что вопрос, что лучше - это холивар! 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

for - это цикл со счетчиком, да синтаксис допускает подобную конструкцию, но синтаксис русского языка тоже допускает написать роман в одном предложении. Почему-то это никто и не думает делать. Тут тоже самое. Хороший стиль подразумевает, чтоб в for был счетчик и условие как-то зависело от него. И это не холивар, а холивар то, что вы устроили. P.S. А вы проверяли действительно ли компилит один и тот же код? А в более сложных случаях?

Скажу честно. Лично не проверял, ибо дизассемблерить мне салбо. Поверил наслово преподу, который дизассемблировал. Ну и вот тоже тема: http://www.linux.org.ru/forum/development/2034180

Что Вы там подразумеваете под более сложными случаями - я не знаю. ИМХО, стандартизация - суть хороший стиль, потому наличие 2-х одинаковых конструкций с разными названиями - не оправданно. Вы можете иметь другое мнение на этот счёт. Остальное без комментариев. Тему с for и while я продолжать не намерен, ибо холивар! 89.162.189.34 08:50, 15 марта 2011 (UTC)Forzi

ЧТОЭТАААААА?????

int function BinarySearch (int[] массив, int леваяГраница, int праваяГраница, int значение) {

  int l = леваяГраница - 1;
  int r = праваяГраница + 1;
  while (r-l>1) {
    int середина = (l+r) / 2;
    if (массив[середина] < значение)
       l = середина;
    else
       r = середина;
  } 
  if (массив[r] ≠ значение)
    return -1; //элемент не найден
  else
    return r;

}

Это что ??? Псевдокод ? Не похоже. С ? Тогда откуда function ? Кто-нибудь пояснит ??? И почему int <русское имя переменной> ???? 94.188.55.33 06:43, 1 июня 2009 (UTC) Я просто мимо проходил...

Поставил шаблон ^{[источник?]} --tim2 13:50, 1 июня 2009 (UTC)

извините, но вы (оскорбление скрыто) (прочитать). это псевдокод.--Leper Messiah 15:13, 1 июня 2009 (UTC)

А Вы, как, извините, крутой кодер, считаете, что в псевдокоде можно писать что угодно? :)

Не далее как несколько месяцев назад, доказывал одному псевдокодеру в одноименной статье в англовики, что следующую строчку писать не следует:

case sign(A[P:=P + L].Key - X)

--tim2 19:52, 1 июня 2009 (UTC)

Это действительно псевдо-код. Скажем прямо, любой алгоритм на несуществующем ЯП — это псевдокод. Другой вопрос, насколько он удобен и понятен. --A.I. 05:36, 2 июня 2009 (UTC)

фишка этого кода в том, что тут явно указано, как «титаны жанра» с красными хэндлами в TopCoder реализуют сей алгоритм. Точнее, один из них. И это проверено вдобавок мной не на одной задаче… Красный хэндл — это серьёзно, да.--Leper Messiah 07:47, 2 июня 2009 (UTC)

См. также Псевдокод (язык описания алгоритмов). Цитирую: "Главная цель использования псевдокода — обеспечить понимание алгоритма человеком, сделать описание более воспринимаемым, чем исходный код на языке программирования". Поэтому, чем проще написано - тем лучше. infovarius 19:36, 2 июня 2009 (UTC)

Я бы предложил использовать русские операторы в псевдокоде и вообще не описывать переменные и не использовать типы. Также желательно расписать, что такое "Массив[r]". infovarius 19:39, 2 июня 2009 (UTC)

Удаленное слово оскорблением не воспринял, тем более, что сказано было не всерьез :) Всерьез согласен с тем, что "чем проще написано - тем лучше", проблема только в том, что многие по-разному понимают, как написать проще. Может, лучше цитировать из источников (т.е. в точности как там написано)? Если над этим думал авторитетный автор и его редактор, а еще, может, и переводчик и редактор перевода - может, это будет наиболее оптимальным?--tim2 20:16, 2 июня 2009 (UTC)

Типы согласен абсолютно не нужны. Но давайте операторы по русски не писать :) --A.I. 05:15, 3 июня 2009 (UTC)

Удивительно, мне одному кажется что разделы <<Поиск элемента отсортированного массива>> и <<Поиск значения монотонной функции>> это суть одно и то же? solitary dreamer 17:53, 3 июня 2009 (UTC)

побитовые операции и деление

Вообще-то в Си и плюсах - да. Да и на эту тему есть авторитетные мнения типа Шилдта.--194.85.27.130 20:34, 27 февраля 2011 (UTC)

Во-первых, оптимизирующие компиляторы и так заменяют x/2 на x >> 1. А даже если и не заменяют, разница, думаю, невелика - вы ее сами замеряли? Во-вторых, я считаю на страницах Википедии ясность кода приоритетнее скорости его исполнения. Не все читатели могут быть хорошо знакомы с C, поэтому лучше использовать более понятный пользователям других языков оператор /, чем специфичный для C оператор >>. А еще лучше вообще заменить на псевдокод. -- X7q 21:20, 27 февраля 2011 (UTC)

Не, как правило не заменяют. Насчет понимания. Во-первых есть комментарий, что это операция деления на 2 на Си. Во-вторых, если даем код на каком-то языке, то выступаем в качестве справочника и следовательно, должны давать наиболее оптимальный код. Критерием оптимальности всех алгоритмов поиска в массиве данных - его скорость. --Abeshenkov 06:22, 28 февраля 2011 (UTC)

Мой gcc заменяет - генерирует одинаковый код для x>>1 и x/2, если x беззнаковое. А вот что насчет корректности? Знаете ли вы, что (a + b) / 2 не совсем правильно, а корректнее вычислять индекс посередине, особенно в случае когда индексы 32-х разрядные, как a + (b - a) / 2? [1]. Предлагаю восстановить версию [2], где про это написано и код более человечный. -- X7q 17:35, 28 февраля 2011 (UTC

Это просто, а подобную ситуацию с арифметическим выражением распознает?--Abeshenkov 18:20, 3 марта 2011 (UTC)

Ну да, переполнение нам может грозить. Это действительно надо поправить. Вариант с Паскалем на мой взгляд, ничем не лучше. Т.к. подавляющее число языков имеют Си-подобный синтаксис. Так что для программиста один фиг. Если пытаться расширить аудиторию читателй, то лучше в псевдокоде.--Abeshenkov 18:20, 3 марта 2011 (UTC)

Код на С с рассуждениями про полезность >> по-моему лучше будет вынести на wikibooks. -- X7q 17:52, 28 февраля 2011 (UTC)

Да, это хороший вариант.--Abeshenkov 18:20, 3 марта 2011 (UTC)

Юнит-тест

Да, я провёл юнит-тест. Теперь код вроде правильный и без излишеств. Даже в коде остались следы моего теста — return FOUND(last); --Mercury 12:42, 6 марта 2014 (UTC)

Иллюстрация

Схема простейшего двоичного поиска. GIF. Надписи на русском.

Oleg Ostapchuk (обс.) 18:14, 13 января 2019 (UTC)

• Гиф-мультипликация с объяснением не очень хороший способ проиллюстрировать алгоритм. Гифки - циклические, поэтому не понятно где начало. У них нет ни кнопки "пауза", ни отмотать назад. Приходится подстраиваться под скорость мультипликации. А скорость чтения и восприятия у всех разная. Поэтому я ценю ваше время, потраченное на анимацию, но я против того, чтобы ставить это в статью. — Алексей Копылов 06:32, 14 января 2019 (UTC)

Показать

Во-первых, спасибо.

Во-вторых, мне бы в голову не пришло такое предлагать, если бы я сам однажды не видел в Википедии иллюстрацию-гифку (возможно, то была статья про дробь).

В-третьих, всё-таки не трудно (я бы даже написал: "нетрудно") (..? ну ладно, может, и трудно :) ... Во всяком случае, трудно не то, что насчёт начала и конца) сообразить, в данном конкретном случае, где у неё начало, где конец: начало "самое широкое", чёрточки по краям; конец: одна голубая черта, надпись "Найден!"... Штукенций Мультимедиа (?) с переходом по нажатию никогда не делал, но имею исходные PNG-файлы (GIF делал из них при помощи GIMP).

В-четвёртых можно сказать, что изначально, да, скорость была высокой, а так - 3 сек. на каждый кадр, кажется.  

Ещё раз спасибо.

Oleg Ostapchuk (обс.) 19:04, 16 января 2019 (UTC)

P.S. Даже сделал .ppsx, но насколько знаю, это не то же самое. В-общем, если надо... Обычно пользуюсь Яндекс-диском, но там оно плохо перезаливается и онлайн редактировать нельзя (только просматривать, кажется). (Это я больше про PNG говорю, ну и про .ppt

Но плохо, что её могут подкорректировать и выдать за свою нерадивые студенты - хотя бы по курсу ИТ в смысле владения PowerPoint...

Хотя плохо соображаю: если что-то такое будет именно в Вики...

;^) Дефрагментация_диска

Про PNG же я писал в смысле исходных картинок, которые можно для того же Flash Player-а ( что ли ) Хотя тут, наверно, подобные технологии не используются...

@ Alexei 13:21, 10 февраля 2019 (UTC)

• Можно использовать видео в формате WebM или Ogg Theora. Это действительно нечасто используется, но это не значит, что это нельзя попробовать. — Алексей Копылов 00:50, 11 февраля 2019 (UTC)

Ok, но пока никогда такого ( видео ) не делал... Или могу скинуть исходники Вам на скайп @ Alexei Oleg Ostapchuk (обс.) 22:43, 14 февраля 2019 (UTC)

P.S. В смысле сначала на Яндекс-диск, а на скайп - ссылку.