Binarne wyszukiwanie posortowanej tablicy 2d - java, tablice, algorytm, wyszukiwanie binarne

Mam program, który przeszukuje tablicę 2D przy użyciuwyszukiwanie binarne. W tym przypadku używam poniższej macierzy i szukam liczb całkowitych 4,12,110,5,111. Program znajduje je wszystkie oprócz 110 i 111, dlaczego tak jest?

       {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;
}

Odpowiedzi:

Wolę powiedzieć, że to mniej więcej niespodziankaże twój algorytm znajduje 4, 5 i 12 w pierwszej kolejności. Powodem tego jest to, że 4 występuje w pierwszej pozycji rzędu, a 5 i 12 spełniają warunek, że są mniejsze niż pierwszy element w następnym rzędzie. Tylko z tego powodu są one odkrywane w drugiej połowie twojego algorytmu. Algorytm jest nieco trudny do odczytania i nie oceniłem magii +/- 1, ale wygląda na to, że algorytm oczekuje, że 110 i 111 wystąpią faktycznie w ostatnim rzędzie (ponieważ zarówno 110, jak i 111 są większe niż 22), gdzie nie są.

Jeśli dobrze zrozumiem, twoje podejście jest wadliweże na podstawie pojedynczej liczby nie jest możliwe stwierdzenie, w którym wierszu się ona pojawi, i to jest to, co starasz się osiągnąć po raz pierwszy. Tak więc dowolny dwufazowy algorytm, który najpierw wybiera wiersz, a następnie przeszukuje kolumnę, musi zawieść.

Z kilkoma ograniczeniami macierzy (każdy wiersz i każda kolumna jest posortowana), nie wygląda na to, że wyszukiwanie binarne w ogóle zadziała: Nawet jeśli twoje granice low i high byłyby to punkty 2D, to niewiele by pomogło. Rozważ dowolny element macierzy, który jest większy niż punkt wyszukiwania. W takim razie wszystko, co możesz powiedzieć, to że jest to punkt wyszukiwania nie poniżej i prawo do tego elementu (podczas gdy kim byłeśMając nadzieję, że uda nam się wyciągnąć wniosek, było to, że było po lewej i powyżej, ale niekoniecznie jest to prawda - może być powyżej i po prawej lub po lewej i poniżej), więc odcinasz tylko zbyt małą część przestrzeni wyszukiwania.

Problem polega na tym, że przyjmujesz fałszywe założenie, że możesz najpierw zablokować wiersz wartości wyszukiwania, a następnie łatwo przeprowadzić wyszukiwanie binarne w tym wierszu. W ogóle tak nie jest.

Dla 110 i 111 pierwszym elementem każdego rzędu jestzawsze mniej niż wartość wyszukiwania, a algorytm dochodzi do fałszywego wniosku, że oznacza to, że wiersz musi być tablicą o indeksie 6 po pierwszej pętli. To po prostu nieprawda.

Powodem, dla którego działa w przypadku małych liczb, jest to, że twój algorytm po prostu ma szczęście, aby zablokować właściwy wiersz w pierwszej pętli ...

Jeden poprawny algorytm szybkiego wyszukiwania na macierzy 2d, w której każdy wiersz i kolumna jest sortowany w porządku rosnącym, wygląda następująco:

1) Zacznij od prawego górnego elementu 2) Pętla: porównaj ten element ez x … .I) jeśli są równe, to zwróć jego pozycję… ii) e <x, a następnie przesuń się to down (jeśli poza matrycą to break return false) ..iii) e> x następnie przesuń go w lewo (jeśli poza granicami matrycy, to złam return false) 3) powtarzaj i), ii) i iii), aż znajdziesz element lub zwrócił fałsz

Znalazłem ten algorytm tutaj: http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

Jest to O (n) dla macierzy n x n.