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

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

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

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

HighPredator · 24.11.2012, 20:19

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

@Khanmon_18 · 24.11.2012, 20:23 **[ТС]**

Согласен, но проблема в том, что организовать поиск надо наиболее эффективным способом

HighPredator · 24.11.2012, 20:36

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

организовать поиск надо наиболее эффективным способом

Бинарный поиск и так эффективен. Что именно вы сделать хотите?

@Khanmon_18 · 24.11.2012, 20:48 **[ТС]**

Я согласен, что бинарный поиск итак эффективен, но представим, что мы решаем следующую задачу: даны перевёрнутые карточки с числами и нам нужно за минимальное число переворачиваний найти карточку с числом N - тогда нам "простой" бинарный поиск не поможет, нужно его модифицировать.

HighPredator · 24.11.2012, 20:59

Khanmon_18, если стопка карточек не отсортирована по числу (номиналу или что там на ней), то и бинарный поиск тут не поможет. И в контексте задачи, мне не ясно при чем тут матрица.

@Khanmon_18 · 24.11.2012, 21:01 **[ТС]**

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

Khanmon_18, если стопка карточек не отсортирована по числу (номиналу или что там на ней), то и бинарный поиск тут не поможет. И в контексте задачи, мне не ясно при чем тут матрица.

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

HighPredator · 24.11.2012, 21:09

То есть у вас есть такое упорядочение:

Если да, то в таком случае можно применить бинарный поиск дважды. Смотрите, первый и последний элементы строк матрицы задают границы (минимальное и максимальное значение в строке). Таким образом, сначала можно бинарным поиском найти строку в которой следует искать нужный элемент, а затем снова бинарным поиском его искать.

@Khanmon_18 · 24.11.2012, 21:18 **[ТС]**

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

То есть у вас есть такое упорядочение

Да, вы правы, спасибо

Комментарий модератора

Правило форума 5.6. Если какой-либо пост на форуме показался вам полезным, нажмите кнопку "Спасибо" внизу самого поста.

@kknop · 11.09.2014, 15:04

Прикольно, что автор согласился, однако рецепт помогает далеко не всегда.
Представьте, к примеру, что числа упорядочены не так, а вот так:
1 4 7
2 6 9
3 8 11
5 10 12
и мы ищем число 6. В какой строке его искать, если по левым/правым границам оно может быть в любой строке?
Да, если бы мы сразу сообразили искать его в столбце, то было бы проще. Но в общем случае искомое число может и в разных столбцах быть.

@Puporev · 11.09.2014, 15:40

Развернуть матрицу в линейный массив и искать, индекс найденного элемента преобразовать в его индексы в матрице.

@kknop · 11.09.2014, 15:49

Да без проблем, но это напрочь игнорит условия построчной и постолбцовой монотонности, и поэтому требует O(N) действий.

@Cyborg Drone · 11.09.2014, 19:07

Можно сделать общую область памяти для двух переменных. Пример:

Pascal
1
2
3
4
const m = 20;
      n = 10;
var mat: array [0..m-1, 0..n-1] of integer;
    vec: array [0..(m-1)*(n-1)] of integer absolute mat;

Если i, j - индексы матрицы, k - индекс вектора, то

Pascal
1
2
i := k div n;
j := k mod m;

Добавлено через 1 минуту
Ну и... нужна сортировка или поиск - используете vec, нужно отображение - используете mat.

Исправлено. Добавлено "или поиск".

@Ромаха · 11.09.2014, 19:30

нужна сортировка

Что за бред?
Ищется самый эффективный вариант.. А Вы приплетаете сортировку
Уж тогда проще за N*M пройти всю матрицу

@Puporev · 11.09.2014, 19:33

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

А Вы приплетаете сортировку

Человек оговорился вместо поиска написал сортировка, а ты уже пасть разинул...

@Cyborg Drone · 11.09.2014, 19:38

Ромаха, если массив неупорядочен (а в подавляющем большинстве случаев так и есть) - перед бинарным поиском требуется сортировка. Почему бред-то?

@Ромаха · 11.09.2014, 19:50

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

Человек оговорился вместо поиска написал сортировка, а ты уже пасть разинул...

Он не оговорился.. Сначала думай-потом говори, идиот

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

Почему бред-то?

Потому что ищем самый эффективный вариант

@Cyborg Drone · 11.09.2014, 20:09

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

Потому что ищем самый эффективный вариант

При отображении двумерного массива на одномерный и получается самый эффективный вариант бинарного поиска для двумерного упорядоченного массива. Что не так?

@bormant · 11.09.2014, 20:09

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

ищем самый эффективный вариант

Это откуда следует?
Было бы условие сформулировано так: "как организовать бинарный поиск в упорядоченном по возрастанию (или убыванию) двумерном массиве(матрице)?", то вопроса про сортировку не возникло бы. Однако, подчёркнутого в вопросе не было. Вы знаете способ организации бинарного поиска на несортированных данных?
Теперь про эффективность. Ради поиска единичного значения сортировка избыточна, никто с этим не спорит. Но и условия о том, что поиск будет единичным, тоже нет. При таком раскладе подготовка исходных данных (сортировка) к многократным бинарным поискам по ним вполне себе эффективный метод. Или что-то неправильно путаю?
Если порядок хранения совпадает с порядком сортировки (слева-направо, сверху вниз), то линеаризация (при помощи absolute, приведения типа, указателя) -- самый малозатратный вариант. А вот если не совпадает, например, массив отсортирован сверху вниз, слева-направо, придется пересчитывать индексы из линейных в прямоугольные и (или) обратно.

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

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

Это откуда следует?

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

Согласен, но проблема в том, что организовать поиск надо наиболее эффективным способом

Еще вопросы?

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .

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

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

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	24.11.2012, 20:19
	Самое простое, что можно выдумать: пройти матрицу построчно и в каждой строке выполнять бинарный поиск. 0

@Khanmon_18 0 / 0 / 0 Регистрация: 24.11.2012 Сообщений: 5
	24.11.2012, 20:23 [ТС]
	Согласен, но проблема в том, что организовать поиск надо наиболее эффективным способом 0

@Khanmon_18 0 / 0 / 0 Регистрация: 24.11.2012 Сообщений: 5
	24.11.2012, 20:48 [ТС]
	Я согласен, что бинарный поиск итак эффективен, но представим, что мы решаем следующую задачу: даны перевёрнутые карточки с числами и нам нужно за минимальное число переворачиваний найти карточку с числом N - тогда нам "простой" бинарный поиск не поможет, нужно его модифицировать. 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	24.11.2012, 20:59
	Khanmon_18, если стопка карточек не отсортирована по числу (номиналу или что там на ней), то и бинарный поиск тут не поможет. И в контексте задачи, мне не ясно при чем тут матрица. 0

@kknop 0 / 0 / 0 Регистрация: 11.09.2014 Сообщений: 2
	11.09.2014, 15:04
	Прикольно, что автор согласился, однако рецепт помогает далеко не всегда. Представьте, к примеру, что числа упорядочены не так, а вот так: 1 4 7 2 6 9 3 8 11 5 10 12 и мы ищем число 6. В какой строке его искать, если по левым/правым границам оно может быть в любой строке? Да, если бы мы сразу сообразили искать его в столбце, то было бы проще. Но в общем случае искомое число может и в разных столбцах быть. 0

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	11.09.2014, 15:40
	Развернуть матрицу в линейный массив и искать, индекс найденного элемента преобразовать в его индексы в матрице. 0

@kknop 0 / 0 / 0 Регистрация: 11.09.2014 Сообщений: 2
	11.09.2014, 15:49
	Да без проблем, но это напрочь игнорит условия построчной и постолбцовой монотонности, и поэтому требует O(N) действий. 0

@Cyborg Drone Модератор 10388 / 5676 / 3399 Регистрация: 17.08.2012 Сообщений: 17,323
	11.09.2014, 19:38
	Ромаха, если массив неупорядочен (а в подавляющем большинстве случаев так и есть) - перед бинарным поиском требуется сортировка. Почему бред-то? 0