Я не могу написать бинарный поиск
Недавно (буквально два года назад) тут пробегала статья Только 10% программистов способны написать двоичный поиск. Двоичный поиск — это классический алгоритм поиска. Мало того, это еще чрезвычайно простой алгоритм, который можно очень легко описать: берем отсортированный массив, смотрим в середину, если не нашли там число, в зависимости от того, что в середине — ищем это число этим же методом либо в левой части, либо в правой, откидывая средний элемент. Для функций также, просто берем не массив, а функцию. Все очень и очень просто, алгоритм описан почти везде, все баги словлены и описаны.
Так вот, я не могу реализовать двоичный поиск. Для меня он ни капельки не тривиален. Наверное, я ненастоящий программист. А ведь так и есть, я всего-лишь студент, но ведь это не оправдание? Если точнее, я не могу реализовать хороший корректный красивый двоичный поиск. Все время у меня вылезает проблема либо с корректностью, либо с красивостью, либо и с тем, и с другим. Так что, да, заголовок немного желтоват.
Прежде чем читать этот топик, напишите свою версию бинарного поиска — для отсортированного массива. Причем, в зависимости от параметра, поиск должен выдавать или первый элемент, или любой из дублирующих. Еще для сравнения, напишите бинарный поиск для функций
Для начала, я буду писать код на C#. Я надеюсь, поклонники других языков с легкостью поймут мой код. Границы поиска я буду представлять в виде полуинтервала [left; right), т.е. точка left включается, а точка right выключается. Для меня полуинтервалы удобнее, к их поведению я уже привык, кроме того, использование полуинтервалов имеет некоторые преимущества при программировании различных алгоритмов (о чем мы поговорим позже). Вообще, использовать полуинтервалы более правильно с точки зрения поддержки «единого стиля программирования», так как я пишу циклы вот так:а не так:
Я буду писать одновременно рекурсивную и итеративную версию, но мне ближе рекурсивная, так что не обессудьте. Для рекурсивной версии мы сделаем вот такую вот красивую обертку:
Первая попытка
Это дает хорошее понимание, что массив надо бить на интервал от [0, 3) и от [4, 7), т.е. от [left, mid) и до [mid + 1, right). Надо заметить, что существовала еще и «нулевая» версия (для статьи), в которой индексы были написаны по памяти, и, естественно, написаны они были неправильно. Самое интересное, что если я пишу алгоритм на листочке, то никаких ошибок не появляется, а если пишу на компьютере, они вылазят как грибы после дождя.
Кстати, теперь можно добавить еще одну причину к использованию полуинтервалов: если у нас есть интервал [left, right], то мы должны его разбить на [left, mid — 1] и [mid + 1; right] (что конечно, чуть проще для запоминания, но весьма странно).
У полуинтервалов различие в индексах равно 1 (одному элементу, который мы выбрасываем), а у интервалов — 2 — магической цифре, взятой с потолка.
Особенно это заметно для сортировки слиянием, где для полуинтервалов различия в индексах нету (массив делится на [left, mid) и [mid, right)), а для интервалов появляется различие равное 1 (так как массив делится на [left, mid] и [mid + 1, right], или [left, mid — 1] и [mid, right]).
Теперь, осталось определить, в какой части массива нужно искать элемент, в зависимости от того, меньше ли средний элемент (array[mid]), чем ключ (key). Сделать это весьма просто — нужно просто подставить сначала один знак, проверить, работает ли программа, а если не работает, то другой :-). Почему-то именно такой способ проверки я и использую. Мне постоянно кажется, что перекомпилировать быстрее, чем «подумать».
Рекурсивно:
Итеративно:
Разбор полетов:
Если внимательно вчитаться в итеративную версию программы, то сразу становится понятно, что если элемента нет, то алгоритм никогда не остановится. Пониманию этого факта очень способствует while(true), которого в рекурсивной версии программы, естественно нет. И хотя я написал кучу реализаций рекурсивных алгоритмов, я все еще иногда сталкиваюсь с тем, что забываю остановить рекурсию. Как можно написать итеративную версию с подвохом, я не знаю.
Вторая попытка
Хорошо, нам надо останавливать алгоритм, когда мы не можем найти элемент в массиве. Но мы же должны что-то возвратить, верно? Или хотя-бы кинуть исключение. Что возвратить? Может быть магическое число (к примеру, -1)? Или заменить int на int? и возвратить null? (int? в c# — это число, которому можно присвоить null). Или может быть вернуть предполагаемое место в массиве, где мог-бы быть элемент, но его нет? Или все-таки кинуть исключение? Или… Это достаточно интересный вопрос, почти такой же как и «в чем смысл жизни?». Кроме интересности, эти вопросы объединяет тот факт, что ответ на оба вопроса можно сформулировать следующим образом: что хотите, то и выбирайте. Конечно, найдутся люди, которые скажут, что нужно возвращать только null, и только null.
Я предпочитаю в таком случае возвратить специальное число -(1 + left), так как, бинарный поиск может использоваться для того, чтобы вставить новый элемент, и потеря информации будет вредна. Конечно, можно написать две версии алгоритма — одна будет возвращать специальное число, а вторая кидать исключение. Хотя это и нехорошо для принципа DRY, если в вашем языке нету чего-нибудь мощного вроде макросов, которые создают функции при компиляции. Ну или можно засунуть в алгоритм параметр, обозначающий что делать.
Кстати, останавливать рекурсию мы будем в случае left == right, т.е., когда интервал стал таким — [left, right). Ну или в случае, когда right — left key
Т.е. если флаг descendingOrder не установлен, то выбор идет как обычно, если установлен, то выбор идет наоборот. Но это «хак», и возможно, что нужно написать какой-нибудь комментарий. Я не знаю, что именно он должен содержать.
Рекурсивно:
Итеративно:
Разбор полетов:
На всякий случай: один из вариантов проверки направления сортировки не учитывал, что массив может быть пуст. Я решил не выделять этот фейл в отдельную попытку.
Попытка №4
Дабы мы не попали на еще одну попытку, сразу скажу, что теперь рекурсию нужно останавливать еще и в случае, когда самый первый элемент из полуинтервала равен ключу. Ну а в случае, когда мы узнали, что средний элемент равен ключу у нас есть два варианта. Либо средний следует за первым и нужно выдавать именно его, ибо первый не равен ключу, поскольку рекурсия еще не остановилась. Либо нужно укорачивать область поиска (см. картинку выше)
Источник
Не работает бинарный поиск
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Неправильно работает бинарный поиск
Доброго времени суток! Бинарный поиск работает некорректно, если в качестве искомого значения взять.
Бинарный поиск, за какое время работает?
за какое время работает бинарный поиск?
Бинарный поиск не работает для ключа с определенным значением
Вообщем, написал бинарный поиск, а он не работает для ключа со значением 9, может кто объяснить.
1. Прежде, чем создавать тему, четко сформулируйте вопрос, с которым Вы собираетесь обращаться.
Он должен быть содержательным, осмысленными и понятными. Например, «Как перемножить элементы массива». Вопросы
типа «Помогите», «Срочно надо», «Не могу сделать» и т.п. таковыми не являются.
5. Создайте тему. С адекватным названием для нее Вы уже определились в первом пункте.
Как можно более полно опишите суть проблемы или вопроса, что было сделано для ее решения и какие результаты получены.
| Меню пользователя @ TheCalligrapher |
Потому что бинарный поиск работает только в отсортированном массиве.
Отсюда вывод: ОТСОРТИРУЙТЕ СНАЧАЛА СВОЙ МАССИВ, который вы сгенерировали рандомно.
Поиск числа в двумерном массиве (бинарный поиск)
Произвожу поиск элемента в массиве двумя способами: линейным(последовательным) поиском и.
Бинарный поиск
Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск.
Бинарный поиск
Здравствуйте, помогите пожалуйста написать функцию бинарного поиска с подсчетом всех найденных.
Бинарный поиск
Здравствуйте, не могу понять как составить алгоритм: нужно найти сумму элементов в массиве, которые.
Источник
Почему не работает бинарный поиск?
Надо сделать поиск по матрице.
k — номер строки.
В чём проблема?
Ниже код на одномерный массив:
Мне надо найти первый элемент из диапазона (0:5)
В данном примере, оно выводит индекс еденицы = 3.
Потому что середина начинается с этого индекса и это значение попадает в диапазон.
Как это исправить?
Если задавать какое-то конкретное число, то находит правильно!
- Вопрос задан более года назад
- 104 просмотра
Проверьте сначала корректность реализации бинарного поиска на одной строке, а затем поместите его в цикл по строкам.
Сейчас у вас какая-то каша вместо программы.
Вы сравниваете pivot с разными значениями. Какое число вы пытаетесь найти?
Вообще говоря, бинарный поиск обычно применяется для поиска одного числа, а не целого диапазона.
Мне кажется проще всего будет просто поискать самое левое число ≥ 0.
Если оно окажется ≤ 5, то это и есть наш ответ, если же нет, то это означает, что ответа не существует, поскольку поиск вернул нам самое левое (то есть маленькое) число из соответствующих условию ≥ 0.
Это и будет бинарный поиск, только реализованный более корректно.
Если вы упростите решаемую задачу, вам будет легче найти ошибку.
Источник
Почему не работает бинарный поиск?
Надо сделать поиск по матрице.
k — номер строки.
В чём проблема?
Ниже код на одномерный массив:
Мне надо найти первый элемент из диапазона (0:5)
В данном примере, оно выводит индекс еденицы = 3.
Потому что середина начинается с этого индекса и это значение попадает в диапазон.
Как это исправить?
Если задавать какое-то конкретное число, то находит правильно!
- Вопрос задан более года назад
- 104 просмотра
Проверьте сначала корректность реализации бинарного поиска на одной строке, а затем поместите его в цикл по строкам.
Сейчас у вас какая-то каша вместо программы.
Вы сравниваете pivot с разными значениями. Какое число вы пытаетесь найти?
Вообще говоря, бинарный поиск обычно применяется для поиска одного числа, а не целого диапазона.
Мне кажется проще всего будет просто поискать самое левое число ≥ 0.
Если оно окажется ≤ 5, то это и есть наш ответ, если же нет, то это означает, что ответа не существует, поскольку поиск вернул нам самое левое (то есть маленькое) число из соответствующих условию ≥ 0.
Это и будет бинарный поиск, только реализованный более корректно.
Если вы упростите решаемую задачу, вам будет легче найти ошибку.
Источник
Бинарный поиск
Добавлено через 4 минуты
К примеру когда я пишу встроенный бин поиск
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Поиск числа в двумерном массиве (бинарный поиск)
Произвожу поиск элемента в массиве двумя способами: линейным(последовательным) поиском и.
Бинарный поиск
Написал программу бинарного поиска элемента v. Не могу понять в чем ошибка, не считает количество.
бинарный поиск
Почему верхний вариант не работает? #include #include #include .
Бинарный поиск
Писал алгоритм бинарного поиска по массиву строк. В результате, почему-то, периодически функция не.
Покажи эту ошибку
Добавлено через 1 минуту
Решение
Бинарный поиск
Здравствуйте, помогите пожалуйста написать функцию бинарного поиска с подсчетом всех найденных.
Бинарный поиск c++
1) последовательного поиска максимального элемента в одномерном динамическом массиве; 2) бинарного.
Бинарный поиск
Реализация на С++: int Search_Binary (int arr, int left, int right, int key) < int midd = 0; .
Бинарный поиск
Здравствуйте, помогите пожалуйста написать бинарный поиск одного элемента, текст читается из файла.
Бинарный поиск
Реализовать алгоритм бинарного поиска количества нулевых элементов двумерного динамического.
Источник
