Бинарный поиск отсортированного массива 2d

Question

У меня есть программа, которая ищет массив 2d, используя двоичный поиск. В этом случае я использую приведенную ниже матрицу и ищу целые числа 4,12,110,5,111. Программа находит все из них, за исключением 110 и 111, почему это?

 {1,3,7,8,8,9,12}, 
     {2,4,8,9,10,30,38}, 
     {4,5,10,20,29,50,60}, 
     {8,10,11,30,50,60,61}, 
     {11,12,40,80,90,100,111}, 
     {13,15,50,100,110,112,120}, 
     {22,27,61,112,119,138,153}, 

public static boolean searchMatrix(int[][] matrix, int p,int n) { 

int low = 0, high = n-1 ; 
while (low < high) { 
int mid = (low + high)/2; 
if (p == matrix[mid][0])return true; 
else if (p < matrix[mid][0]) high = mid - 1; 
else if (p < matrix[mid+1][0]) { low = mid; break; } 
else low = mid + 1; 
} 


int row = low; 
low = 0; high = matrix[row].length - 1; 
while (low <= high) { 
int mid = (low + high)/2; 
if (p == matrix[row][mid]) return true; 
else if (p < matrix[row][mid]) high = mid - 1; 
else low = mid + 1; 
} 

return false; 
} 

Answer 1

Я бы сказал, что это более или менее удивительно, что ваш алгоритм действительно находит 4, 5, и 12, в первую очередь. Причиной этого является то, что 4 встречается в первой позиции строки, а 5 и 12 удовлетворяют условию, что они меньше первого элемента в следующей строке. Только из-за этого они обнаруживаются во второй половине вашего алгоритма. Алгоритм немного трудно читать, и я не оценил магию +/- 1, но, похоже, алгоритм ожидает, что 110 и 111 произойдут фактически в последней строке (так как 110 и 111 больше 22), где они не.

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

С некоторыми ограничениями вы имеете на вашей матрице (каждая строка и каждый столбец сортируется), это не похоже, бинарный поиск будет работать на всех: Даже если ваши оценки low и high бы 2D точки это не помогло бы много. Рассмотрим любой элемент матрицы, который больше вашей точки поиска. Тогда вы можете только сказать, что ваша поисковая точка не ниже и Право этого элемента (тогда как вы надеялись сделать вывод, что он остался и выше, но это не обязательно так - это может быть выше и справа или слева и ниже), так что вы отрезаете только слишком малую часть пространства поиска.

Answer 2

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

Для 110 и 111 первый элемент каждой строки всегда меньше вашего значения поиска, и ваш алгоритм приходит к ложному выводу, что это означает, что ваша строка должна быть массивом с индексом 6 после первого цикла. Это просто неправда.

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

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

1) Начните с верхним правым элементом 2) Loop: сравнить этот элемент е с й ... й), если они равны, то вернуть свою позицию ... б) е < x затем переместить он вниз (если из граничной матрицы, тогда отменить возврат false) ..iii) е> х, то переместите его влево (если из границы матрицы затем перерыв возвращение ложным) 3) повторить I), б) и в), пока не найдете элемент или возвращенное ложное

Я нашел этот алгоритм здесь: http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

Это O (n) для матрицы nxn.