Бинарный поиск в матрице

@Khanmon_18 · Регистрация: 24.11.2012

Студворк — интернет-сервис помощи студентам

Подскажите, пожалуйста, как организовать бинарный поиск в двумерном массиве(матрице)?

@Puporev · 11.09.2014, 20:22

Что за мода, поднять тему двухлетней давности и спорить до усрачки...
А этот kknop, вообще похоже тролль жирный...

@Ромаха · 11.09.2014, 20:29

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

Новичок · 12.09.2014, 20:19

Сообщение от Ромаха

лишь говорит о его домыслах по поводу решения задачи..

Но ТС разве написал полное условие?! Или телепаты должны были угадать, что он хотел?! Он написал, что бинарный поиск хочет юзать. Откуда нам знать что он хотел?!

@Ромаха · 13.09.2014, 02:26

Сообщение от Новичок

Он написал, что бинарный поиск хочет юзать.

Он написал, что хочет юзать его максимально эффективно
Поэтому, чтобы понять, что сортировка матрицы - бред и ересь, не нужно быть телепатом
Еще вопросы?

@bormant · 13.09.2014, 09:38

Сообщение от Ромаха

Еще вопросы?

Только ответы. http://www.gramota.ru/slovari/... 2%E0%F2%FC
Обратите внимание на буквальное значение слова "организовать" в 3 случае -- "подготовить и осуществить".
Бинарный поиск на произвольных данных невозможен, данные должны быть подготовлены определённым образом -- отсортированы.
Поэтому организация бинарного поиска (да, включает создание необходимых условий) несколько шире выполнения бинарного поиска.

PS. Форум портит при переходе по ссылке амперсанд.

@Ромаха · 13.09.2014, 14:16

А фигня вопрос, давай обсудим..
Сортировка.. Это logN*N.. у нас матрица.. поэтому log(N*M)*(N+M).. так?
Бинарный поиск по каждой строчке - это log(M)*N.. Бинго..
Еще вопросы?

@bormant · 13.09.2014, 23:53

Ромаха,
зачем искать по каждой строчке?

@Ромаха · 14.09.2014, 11:10

Сообщение от bormant

зачем искать по каждой строчке?

Нам нужно найти элемент в матрице, которая упорядочена по определенному правилу..
Известно, что строки упорядочены. Поэтому можно сделать так :
Для каждой строки прогнать бинарный поиск. Получим log(n)*m..

@Cyborg Drone · 14.09.2014, 11:46

Ромаха, а поиск сразу по всей упорядоченной матрице даст log₂(n*m). Быстрее, чем по каждой строчке. Ну и... Зачем искать по каждой строчке?

@Ромаха · 14.09.2014, 11:49

Она неупорядочена для бинарного поиска!

@Cyborg Drone · 14.09.2014, 12:33

Сообщение от Ромаха

Она неупорядочена для бинарного поиска!

Где в теме написано, кроме Вашей ссылки на никак не относящуюся к вопросу темы задачу, как именно матрица упорядочена?

Ещё раз, если одного раза мало.
- Почему кто-то должен знать, что имел ввиду ТС? Не требуется ничего такого знать, всё должно быть в задании.
- ТС написал, что этот вопрос относится к указанной Вами задаче? Нет.
- Он хотя бы создал тему с указанной Вами задачей? Нет.
Вот и объясните, какие предпосылки позволили Вам прийти к выводу, что указанная Вами задача как-то связана с вопросом темы?

Поэтому и считаю, что матрица будет мною упорядочена так, как мне нужно.

@Ромаха · 14.09.2014, 12:35

Сообщение от Cyborg Drone

Где в теме написано, кроме Вашей ссылки на никак не относящуюся к вопросу темы задачу, как именно матрица упорядочена?

Вот тут

Сообщение от Khanmon_18

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

@Cyborg Drone · 14.09.2014, 13:16

Ах да. Насчёт задачи писал. Извиняюсь.

Добавлено через 33 минуты
Тогда оптимизация возможна. И здесь лучше использовать бинарный поиск. Сужаем область поиска (уменьшаем размер матрицы без просмотра всех элементов) следующим образом:

0 (для всего алгоритма: если в процессе переворота очередной карточки найдётся нужный элемент, то ура);
1 выявляем те строки и столбцы, первый элемент которых больше искомого, очевидно, нужной карточки в этих строках и столбцах нет;
2 выявляем те строки и столбцы, последний элемент которых меньше искомого, очевидно, нужной карточки в этих строках и столбцах нет;
3 повторяем шаги 1 и 2 до тех пор, пока не обнаружим искомый элемент.

Не по теме:

Вот ведь... Код написать уже некогда...

@Puporev · 14.09.2014, 13:18

Сообщение от Cyborg Drone

Код написать уже некогда...

А кому он сейчас нужен? Автору темы, что 2 года назад ее создал? Если потомкам, то еще напишешь..

@Ромаха · 14.09.2014, 13:20

Ну это-то понятно..
Думаю, что есть что-то еще..
Можно как-то еще улучшить..

@Cyborg Drone · 14.09.2014, 13:26

Сообщение от Puporev

А кому он сейчас нужен?

Ну, тому, кому понадобится решение данной задачи... Я так понял, что её всё ещё кому-то задают.

Ромаха, так, навскидку... Может, по главной и побочной диагонали отсекать (не спорьте, эти диагонали определены и для неквадратных матриц)...

Не по теме:

Всё, я в отпуске.

@Ромаха · 14.09.2014, 13:40

Сообщение от Cyborg Drone

Я так понял, что её всё ещё кому-то задают.

Если это подкол в мою сторону, то Вы ни разу не правы.. Я тут случайно..

Сообщение от Cyborg Drone

Может, по главной и побочной диагонали отсекать

Вообще не в ту сторону (ИМХО)

Новые блоги и статьи Все статьи Все блоги /
GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP and_y87 12.10.2026 10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .	GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP and_y87 12.10.2026 10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .	День 5 из 28: Codex подсказывает следующий запрос and_y87 12.10.2026 9 октября 2026 года OpenAI запустила бету Composer predictions — подсказок следующего сообщения в текущем диалоге Codex. Это помощь с формулировкой запроса, а не автоматическое продолжение задачи. . . .	Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@Khanmon_18 0 / 0 / 0 Регистрация: 24.11.2012 Сообщений: 5

	Бинарный поиск в матрице 24.11.2012, 20:14. Показов 5023. Ответов 36 Метки нет (Все метки) Подскажите, пожалуйста, как организовать бинарный поиск в двумерном массиве(матрице)? 0

@Puporev Почетный модератор 64320 / 47616 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	11.09.2014, 20:22
	Что за мода, поднять тему двухлетней давности и спорить до усрачки... А этот kknop, вообще похоже тролль жирный... 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	11.09.2014, 20:29
	Думаю, что задача взята из тыц. А то, что ТС начал разговор про бинарный поиск, лишь говорит о его домыслах по поводу решения задачи.. Поэтому все Ваши решения про слив и сортировку - ересь 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	13.09.2014, 14:16
	А фигня вопрос, давай обсудим.. Сортировка.. Это logNN.. у нас матрица.. поэтому log(NM)(N+M).. так? Бинарный поиск по каждой строчке - это log(M)N.. Бинго.. Еще вопросы? 0

@bormant Модератор 7818 / 4637 / 2837 Регистрация: 22.11.2013 Сообщений: 13,159 Записей в блоге: 1
	13.09.2014, 23:53
	Ромаха, зачем искать по каждой строчке? 0

@Cyborg Drone Модератор 10478 / 5772 / 3413 Регистрация: 17.08.2012 Сообщений: 17,536
	14.09.2014, 11:46
	Ромаха, а поиск сразу по всей упорядоченной матрице даст log₂(n*m). Быстрее, чем по каждой строчке. Ну и... Зачем искать по каждой строчке? 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	14.09.2014, 11:49
	Она неупорядочена для бинарного поиска! 0

@Cyborg Drone Модератор 10478 / 5772 / 3413 Регистрация: 17.08.2012 Сообщений: 17,536
	14.09.2014, 13:16
	Ах да. Насчёт задачи писал. Извиняюсь. Добавлено через 33 минуты Тогда оптимизация возможна. И здесь лучше использовать бинарный поиск. Сужаем область поиска (уменьшаем размер матрицы без просмотра всех элементов) следующим образом: 0 (для всего алгоритма: если в процессе переворота очередной карточки найдётся нужный элемент, то ура); 1 выявляем те строки и столбцы, первый элемент которых больше искомого, очевидно, нужной карточки в этих строках и столбцах нет; 2 выявляем те строки и столбцы, последний элемент которых меньше искомого, очевидно, нужной карточки в этих строках и столбцах нет; 3 повторяем шаги 1 и 2 до тех пор, пока не обнаружим искомый элемент. Не по теме: Вот ведь... Код написать уже некогда... 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	14.09.2014, 13:20
	Ну это-то понятно.. Думаю, что есть что-то еще.. Можно как-то еще улучшить.. 0