Jak wyszukać liczbę w tablicy 2D posortowanej od lewej do prawej i od góry do dołu?

Niedawno zadano mi to pytanie do wywiadu i jestem ciekawy, jakie byłoby dobre rozwiązanie.

Powiedzmy, że otrzymałem tablicę 2d, w której wszystkie liczby w tablicy są w kolejności rosnącej od lewej do prawej i od góry do dołu.

Jaki jest najlepszy sposób wyszukiwania i określania, czy liczba docelowa znajduje się w tablicy?

Teraz moją pierwszą skłonnością jest skorzystanie z wyszukiwania binarnego, ponieważ moje dane są posortowane. Potrafię określić, czy liczba znajduje się w jednym wierszu w czasie O (log N). Jednak to 2 kierunki mnie zniechęcają.

Innym rozwiązaniem, które moim zdaniem może zadziałać, jest rozpoczęcie gdzieś pośrodku. Jeśli środkowa wartość jest mniejsza niż mój cel, mogę być pewien, że znajduje się w lewej kwadratowej części macierzy od środka. Następnie przesuwam się po przekątnej i ponownie sprawdzam, zmniejszając rozmiar kwadratu, w którym może znajdować się cel, dopóki nie ustalę docelowej liczby.

Czy ktoś ma jakieś dobre pomysły na rozwiązanie tego problemu?

Przykładowa tablica:

Posortowane od lewej do prawej, od góry do dołu.

1  2  4  5  6  
2  3  5  7  8  
4  6  8  9  10  
5  8  9  10 11  

Oto proste podejście:

1. Zacznij od lewego dolnego rogu.
2. Jeśli cel jest mniejszy niż ta wartość, musi znajdować się nad nami, więc przesuń się o jeden w górę .
3. W przeciwnym razie wiemy, że cel nie może znajdować się w tej kolumnie, więc przesuń w prawo .
4. Idź do 2.

W przypadku NxMtablicy to działa O(N+M). Myślę, że trudno byłoby zrobić coś lepszego. :)

Edycja: dużo dobrej dyskusji. Mówiłem o ogólnym przypadku powyżej; Oczywiście, jeśli Nalbo M są małe, można użyć metody przeszukiwania binarnego to zrobić w czymś zbliżającym czas logarytmiczną.

Oto kilka szczegółów dla ciekawskich:

Historia

Ten prosty algorytm nazywa się wyszukiwaniem siodłowym . Jest już od jakiegoś czasu i jest optymalny, kiedy N == M. Niektóre odniesienia:

• David Gries, Nauka o programowaniu . Springer-Verlag, 1989 .
• Edsgar Dijkstra, The Saddleback Search . Uwaga EWD-934, 1985 .

Jednakże, gdy N < Mintuicja podpowiada, że ​​wyszukiwanie binarne powinno być w stanie zrobić lepiej niż O(N+M): Na przykład, gdy N == 1czyste wyszukiwanie binarne będzie przebiegać w czasie logarytmicznym, a nie liniowym.

Najgorszy przypadek

Richard Bird zbadał tę intuicję, że wyszukiwanie binarne może ulepszyć algorytm Saddleback w artykule z 2006 roku:

• Richard S. Bird, Improving Saddleback Search: A Lesson in Algorithm Design , in Mathematics of Program Construction, str. 82-89, tom 4014, 2006 .

Używając dość nietypowej techniki konwersacyjnej, Bird pokazuje nam, że N <= Mproblem ten ma dolną granicę Ω(N * log(M/N)). To wiązanie ma sens, ponieważ daje nam liniową wydajność kiedy N == Mi logarytmiczną kiedy N == 1.

Algorytmy dla tablic prostokątnych

Jedno podejście, które wykorzystuje wyszukiwanie binarne wiersz po wierszu, wygląda następująco:

1. Zacznij od prostokątnej tablicy, gdzie N < M. Powiedzmy, że Nto wiersze i Mkolumny.
2. Wykonaj wyszukiwanie binarne w środkowym wierszu dla value. Jeśli to znajdziemy, skończymy.
3. W przeciwnym razie znaleźliśmy sąsiednią parę liczb si ggdzie s < value < g.
4. Prostokąt liczb powyżej i na lewo od sjest mniejszy niż value, więc możemy go wyeliminować.
5. Prostokąt poniżej i po prawej stronie gjest większy niż value, więc możemy go wyeliminować.
6. Przejdź do kroku (2) dla każdego z dwóch pozostałych prostokątów.

Pod względem złożoności najgorszego przypadku algorytm ten log(M)działa w celu wyeliminowania połowy możliwych rozwiązań, a następnie rekurencyjnie wywołuje się dwukrotnie w przypadku dwóch mniejszych problemów. Musimy powtórzyć mniejszą wersję tej log(M)pracy dla każdego wiersza, ale jeśli liczba wierszy jest niewielka w porównaniu do liczby kolumn, to możliwość wyeliminowania wszystkich tych kolumn w czasie logarytmicznym zaczyna być opłacalna .

Daje to algorytmowi złożoność T(N,M) = log(M) + 2 * T(M/2, N/2), którą Bird wykazuje O(N * log(M/N)).

Inne podejście opublikowane przez Craiga Gidneya opisuje algorytm podobny do podejścia powyżej: bada wiersz po kolei przy użyciu rozmiaru kroku M/N. Jego analiza pokazuje, że to również przekłada się na O(N * log(M/N))wydajność.

Porównanie wydajności

Analiza Big-O jest dobra i dobra, ale jak dobrze te podejścia sprawdzają się w praktyce? Poniższy wykres przedstawia cztery algorytmy dla coraz bardziej „kwadratowych” tablic:

(Algorytm „naiwny” po prostu przeszukuje każdy element tablicy. Algorytm „rekurencyjny” został opisany powyżej. Algorytm „hybrydowy” jest implementacją algorytmu Gidneya . Dla każdego rozmiaru tablicy wydajność mierzono przez synchronizację każdego algorytmu ze stałym zestawem 1 000 000 losowo generowanych tablic).

Kilka ważnych punktów:

• Zgodnie z oczekiwaniami algorytmy „wyszukiwania binarnego” zapewniają najlepszą wydajność w przypadku tablic prostokątnych, a algorytm Saddleback działa najlepiej na tablicach kwadratowych.
• Algorytm Saddleback działa gorzej niż „naiwny” algorytm dla tablic jednowymiarowych, prawdopodobnie dlatego, że wykonuje wielokrotne porównania każdego elementu.
• Wydajność, którą algorytmy „wyszukiwania binarnego” przejmują na tablicach kwadratowych, jest prawdopodobnie spowodowana narzutem wynikającym z wykonywania powtarzających się wyszukiwań binarnych.

Podsumowanie

Sprytne użycie wyszukiwania binarnego może zapewnić O(N * log(M/N)wydajność zarówno dla tablic prostokątnych, jak i kwadratowych. O(N + M)Algorytm „saddleback” jest o wiele prostsze, ale cierpi z powodu degradacji wydajności jako tablice stają się coraz bardziej prostokątny.

Ten problem wymaga Θ(b lg(t))czasu, gdzie b = min(w,h)i t=b/max(w,h). Rozwiązanie omawiam w tym wpisie na blogu .

Dolna granica

Przeciwnik może zmusić algorytm do zadawania Ω(b lg(t))zapytań, ograniczając się do głównej przekątnej:

Legenda: białe pola to mniejsze elementy, szare pola to większe elementy, żółte pola to mniejsze lub równe elementy, a pomarańczowe pola to większe lub równe elementy. Przeciwnik wymusza na rozwiązaniu dowolną żółtą lub pomarańczową komórkę, której algorytm zapyta ostatnio.

Zauważ, że istnieją bniezależne posortowane listy rozmiarów t, które wymagają Ω(b lg(t))całkowitego wyeliminowania zapytań.

Algorytm

1. (Załóżmy bez utraty ogólności, że w >= h)
2. Porównaj element docelowy z komórką tpo lewej stronie prawego górnego rogu prawidłowego obszaru
   • Jeśli element komórki pasuje, zwróć bieżącą pozycję.
   • Jeśli element komórki jest mniejszy niż element docelowy, usuń pozostałe tkomórki w wierszu za pomocą wyszukiwania binarnego. Jeśli podczas wykonywania tej czynności zostanie znaleziony pasujący element, wróć z jego pozycją.
   • W przeciwnym razie element komórki jest czymś więcej niż elementem docelowym, co eliminuje tkrótkie kolumny.
3. Jeśli nie ma żadnego ważnego obszaru, zwraca błąd
4. Przejdź do kroku 2

Znajdowanie przedmiotu:

Określenie pozycji nie istnieje:

Legenda: białe komórki to mniejsze elementy, szare komórki to większe elementy, a zielona komórka to taki sam element.

Analiza

b*tDo wyeliminowania są krótkie kolumny. Trzeba bwyeliminować długie rzędy. Eliminacja długich rzędów kosztuje O(lg(t))czas. Eliminacja tkrótkich kolumn kosztuje O(1)czas.

W najgorszym przypadku będziemy musieli wyeliminować każdą kolumnę i każdy wiersz, co zajmuje trochę czasu O(lg(t)*b + b*t*1/t) = O(b lg(t)).

Zwróć uwagę, że zakładam lgzaciski do wyniku powyżej 1 (tj lg(x) = log_2(max(2,x)).). Dlatego kiedy w=h, czyli t=1otrzymujemy oczekiwaną granicę O(b lg(1)) = O(b) = O(w+h).

Kod

public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) {
    if (grid == null) throw new ArgumentNullException("grid");
    comparer = comparer ?? Comparer<T>.Default;

    // check size
    var width = grid.Count;
    if (width == 0) return null;
    var height = grid[0].Count;
    if (height < width) {
        var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
        if (result == null) return null;
        return Tuple.Create(result.Item2, result.Item1);
    }

    // search
    var minCol = 0;
    var maxRow = height - 1;
    var t = height / width;
    while (minCol < width && maxRow >= 0) {
        // query the item in the minimum column, t above the maximum row
        var luckyRow = Math.Max(maxRow - t, 0);
        var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
        if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);

        // did we eliminate t rows from the bottom?
        if (cmpItemVsLucky < 0) {
            maxRow = luckyRow - 1;
            continue;
        }

        // we eliminated most of the current minimum column
        // spend lg(t) time eliminating rest of column
        var minRowInCol = luckyRow + 1;
        var maxRowInCol = maxRow;
        while (minRowInCol <= maxRowInCol) {
            var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
            var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
            if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
            if (cmpItemVsMid > 0) {
                minRowInCol = mid + 1;
            } else {
                maxRowInCol = mid - 1;
                maxRow = mid - 1;
            }
        }

        minCol += 1;
    }

    return null;
}

W przypadku tego problemu zastosowałbym strategię „dziel i rządź”, podobną do tej, którą sugerowałeś, ale szczegóły są nieco inne.

Będzie to przeszukiwanie rekurencyjne w podzakresach macierzy.

Na każdym kroku wybierz element ze środka zakresu. Jeśli znaleziona wartość jest tym, czego szukasz, to koniec.

W przeciwnym razie, jeśli znaleziona wartość jest mniejsza niż wartość, której szukasz, wiesz, że nie ma jej w ćwiartce powyżej i na lewo od Twojej bieżącej pozycji. Zatem przeszukaj rekurencyjnie dwa podzakresy: wszystko (wyłącznie) poniżej aktualnej pozycji i wszystko (wyłącznie) po prawej stronie, które jest na lub powyżej bieżącej pozycji.

W przeciwnym razie (znaleziona wartość jest większa niż wartość, której szukasz) wiesz, że nie ma jej w ćwiartce poniżej i po prawej stronie Twojej bieżącej pozycji. Zatem przeszukaj rekurencyjnie dwa podzakresy: wszystko (wyłącznie) na lewo od bieżącej pozycji i wszystko (wyłącznie) powyżej bieżącej pozycji, które znajduje się w bieżącej kolumnie lub kolumnie po prawej stronie.

I ba-da-bing, znalazłeś to.

Zwróć uwagę, że każde wywołanie rekurencyjne dotyczy tylko bieżącego podzakresu, a nie (na przykład) WSZYSTKICH wierszy powyżej bieżącej pozycji. Tylko te w obecnym podzakresie.

Oto pseudokod dla Ciebie:

bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)

if (minX == maxX and minY == maxY and arr[minX,minY] != value)
    return false
if (arr[minX,minY] > value) return false;  // Early exits if the value can't be in 
if (arr[maxX,maxY] < value) return false;  // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
    print nextX,nextY
    return true
}
else if (arr[nextX,nextY] < value)
{
    if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
        return true
    return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
    if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
        return true
    reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}

Dwie główne odpowiedzi udzielone do tej pory wydają się być prawdopodobnie O(log N)„metodą zygzaka” i O(N+M)metodą wyszukiwania binarnego. Pomyślałem, że przeprowadzę testy, porównując te dwie metody z różnymi konfiguracjami. Oto szczegóły:

W każdym teście tablica ma kwadrat N x N, przy czym N waha się od 125 do 8000 (największa, z jaką mogłem obsłużyć sterta JVM). Dla każdego rozmiaru tablicy wybrałem losowe miejsce w tablicy, aby umieścić pojedynczy 2. Następnie umieściłem 3wszędzie możliwe (po prawej i poniżej 2), a następnie wypełniłem resztę tablicy1. Niektórzy z wcześniejszych komentatorów wydawali się sądzić, że tego typu konfiguracja zapewniłaby najgorszy czas działania obu algorytmów. Dla każdego rozmiaru tablicy wybrałem 100 różnych losowych lokalizacji dla 2 (celu wyszukiwania) i przeprowadziłem test. Zarejestrowałem średni czas działania i najgorszy czas działania dla każdego algorytmu. Ponieważ działo się to zbyt szybko, aby uzyskać dobre odczyty ms w Javie, i ponieważ nie ufam nanoTime () Javy, powtórzyłem każdy test 1000 razy, aby za każdym razem dodać jednakowy współczynnik obciążenia. Oto wyniki:

Zygzak pobił binarny w każdym teście zarówno dla czasów średniego, jak i najgorszego przypadku, jednak wszystkie mieszczą się w zakresie rzędu wielkości siebie mniej więcej.

Oto kod Java:

public class SearchSortedArray2D {

    static boolean findZigZag(int[][] a, int t) {
        int i = 0;
        int j = a.length - 1;
        while (i <= a.length - 1 && j >= 0) {
            if (a[i][j] == t) return true;
            else if (a[i][j] < t) i++;
            else j--;
        }
        return false;
    }

    static boolean findBinarySearch(int[][] a, int t) {
        return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
    }

    static boolean findBinarySearch(int[][] a, int t,
            int r1, int c1, int r2, int c2) {
        if (r1 > r2 || c1 > c2) return false; 
        if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
        if (a[r1][c1] > t) return false;
        if (a[r2][c2] < t) return false;

        int rm = (r1 + r2) / 2;
        int cm = (c1 + c2) / 2;
        if (a[rm][cm] == t) return true;
        else if (a[rm][cm] > t) {
            boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
            boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
            return (b1 || b2);
        } else {
            boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
            boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
            return (b1 || b2);
        }
    }

    static void randomizeArray(int[][] a, int N) {
        int ri = (int) (Math.random() * N);
        int rj = (int) (Math.random() * N);
        a[ri][rj] = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == ri && j == rj) continue;
                else if (i > ri || j > rj) a[i][j] = 3;
                else a[i][j] = 1;
            }
        }
    }

    public static void main(String[] args) {

        int N = 8000;
        int[][] a = new int[N][N];
        int randoms = 100;
        int repeats = 1000;

        long start, end, duration;
        long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
        long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
        long zigSum = 0, zigAvg;
        long binSum = 0, binAvg;

        for (int k = 0; k < randoms; k++) {
            randomizeArray(a, N);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findZigZag(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            zigSum += duration;
            zigMin = Math.min(zigMin, duration);
            zigMax = Math.max(zigMax, duration);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            binSum += duration;
            binMin = Math.min(binMin, duration);
            binMax = Math.max(binMax, duration);
        }
        zigAvg = zigSum / randoms;
        binAvg = binSum / randoms;

        System.out.println(findZigZag(a, 2) ?
                "Found via zigzag method. " : "ERROR. ");
        //System.out.println("min search time: " + zigMin + "ms");
        System.out.println("max search time: " + zigMax + "ms");
        System.out.println("avg search time: " + zigAvg + "ms");

        System.out.println();

        System.out.println(findBinarySearch(a, 2) ?
                "Found via binary search method. " : "ERROR. ");
        //System.out.println("min search time: " + binMin + "ms");
        System.out.println("max search time: " + binMax + "ms");
        System.out.println("avg search time: " + binAvg + "ms");
    }
}

To jest krótki dowód na dolną granicę problemu.

Nie da się tego zrobić lepiej niż czas liniowy (pod względem wymiarów tablicy, a nie liczby elementów). W poniższej tablicy każdy z elementów oznaczonych jako *może mieć wartość 5 lub 6 (niezależnie od pozostałych). Więc jeśli twoją wartością docelową jest 6 (lub 5), algorytm musi zbadać je wszystkie.

1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10

Oczywiście dotyczy to również większych tablic. Oznacza to, że ta odpowiedź jest optymalna.

Aktualizacja: Jak wskazał Jeffrey L Whitledge, optymalne jest jedynie to, że asymptotyczna dolna granica czasu działania w stosunku do wielkości danych wejściowych (traktowana jako pojedyncza zmienna). Czas działania traktowany jako funkcja dwóch zmiennych na obu wymiarach tablicy można poprawić.

Myślę, że tutaj jest odpowiedź i działa dla każdego rodzaju posortowanej macierzy

bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
    if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
    if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
    if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
    if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;

    int xnew = (xmin + xmax)/2;
    int ynew = (ymin + ymax)/2;

    if (arr[xnew][ynew] == key) return true;
    if (arr[xnew][ynew] < key)
    {
        if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
    } else {
        if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
    }
}

Interesujące pytanie. Rozważ ten pomysł - stwórz jedną granicę, w której wszystkie liczby są większe niż cel, a drugą, w której wszystkie liczby są mniejsze niż cel. Jeśli coś zostanie pomiędzy nimi, to twój cel.

Jeśli w twoim przykładzie szukam 3, czytam w pierwszym wierszu, aż trafię 4, a następnie poszukaj najmniejszej sąsiedniej liczby (w tym przekątnych) większej niż 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Teraz robię to samo dla liczb mniejszych niż 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Teraz pytam, czy jest coś wewnątrz tych dwóch granic? Jeśli tak, to musi być 3. Jeśli nie, to nie ma 3. Rodzaj pośredni, ponieważ tak naprawdę nie znajduję liczby, po prostu wnioskuję, że musi tam być. Ma to dodatkowy bonus polegający na liczeniu WSZYSTKICH 3.

Wypróbowałem to na kilku przykładach i wydaje się, że działa OK.

Najlepszą opcją jest wyszukiwanie binarne po przekątnej tablicy. Możemy dowiedzieć się, czy element jest mniejszy lub równy elementom na przekątnej.

A. Przeprowadź wyszukiwanie binarne w tych wierszach, w których może znajdować się numer docelowy.

B. Zrób z tego wykres: poszukaj liczby, biorąc zawsze najmniejszy nieodwiedzony węzeł sąsiedni i cofając się, gdy zostanie znaleziona zbyt duża liczba

Wyszukiwanie binarne byłoby najlepszym podejściem, imo. Zaczynając od 1/2 x, 1/2 y przeciąć go na pół. IE kwadrat 5x5 to coś w rodzaju x == 2 / y == 3. Zaokrągliłem jedną wartość w dół i jedną w górę do lepszej strefy w kierunku docelowej wartości.

Dla jasności następna iteracja dałaby coś takiego jak x == 1 / y == 2 LUB x == 3 / y == 5

Cóż, na początek załóżmy, że używamy kwadratu.

1 2 3
2 3 4
3 4 5

1. Wyszukiwanie kwadratu

Użyłbym wyszukiwania binarnego na przekątnej. Celem jest zlokalizowanie mniejszej liczby, która nie jest dokładnie niższa niż liczba docelowa.

Powiedzmy, że szukam na 4przykład, a następnie zlokalizuję 5w (2,2).

Następnie, jestem pewien, że jeśli 4znajduje się w tabeli, to jest w położeniu, albo (x,2)czy (2,x)się xw[0,2] . Cóż, to tylko 2 wyszukiwania binarne.

Złożoność nie jest zniechęcająca: O(log(N))(3 wyszukiwania binarne według zakresów długości N)

2. Poszukiwanie prostokąta, naiwne podejście

Oczywiście trochę bardziej się komplikuje Ni Mróżni się (prostokątem), rozważmy ten zdegenerowany przypadek:

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17

I powiedzmy, że szukam 9... Podejście ukośne jest nadal dobre, ale definicja diagonalnych się zmienia. Oto moja przekątna [1, (5 or 6), 17]. Powiedzmy, że odebrałem [1,5,17], to wiem, że jeśli 9jest w tabeli, to albo w podpunkcie:

            5  6  7  8
            6  7  8  9
10 11 12 13 14 15 16

To daje nam 2 prostokąty:

5 6 7 8    10 11 12 13 14 15 16
6 7 8 9

Więc możemy powtórzyć! prawdopodobnie zaczynając od tego z mniejszą liczbą elementów (choć w tym przypadku nas to zabija).

Powinienem zaznaczyć, że jeśli jeden z wymiarów jest mniejszy niż 3, nie możemy zastosować metod diagonalnych i musimy użyć wyszukiwania binarnego. Tutaj oznaczałoby to:

• Zastosuj wyszukiwanie binarne do 10 11 12 13 14 15 16, nie znaleziono
• Zastosuj wyszukiwanie binarne do 5 6 7 8, nie znaleziono
• Zastosuj wyszukiwanie binarne do 6 7 8 9, nie znaleziono

Jest to trudne, ponieważ aby uzyskać dobrą wydajność, możesz chcieć rozróżnić kilka przypadków, w zależności od ogólnego kształtu ...

3. Poszukiwanie prostokąta, brutalne podejście

Byłoby znacznie łatwiej, gdybyśmy mieli do czynienia z kwadratem ... więc po prostu wyrównajmy rzeczy.

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17
17 .  .  .  .  .  .  17
.                    .
.                    .
.                    .
17 .  .  .  .  .  .  17

Mamy teraz kwadrat.

Oczywiście prawdopodobnie NIE utworzymy tych wierszy, moglibyśmy je po prostu emulować.

def get(x,y):
  if x < N and y < M: return table[x][y]
  else: return table[N-1][M-1]            # the max

więc zachowuje się jak kwadrat bez zajmowania większej ilości pamięci (kosztem szybkości pewnie w zależności od cache ... no cóż: p)

EDYTOWAĆ:

Źle zrozumiałem pytanie. Jak wskazują komentarze, działa to tylko w bardziej ograniczonym przypadku.

W języku takim jak C, który przechowuje dane w kolejności od głównych wierszy, po prostu potraktuj je jako tablicę 1D o rozmiarze n * m i użyj wyszukiwania binarnego.

Mam rekursywne rozwiązanie typu Divide & Conquer. Podstawowy pomysł na jeden krok to: Wiemy, że lewy górny (LU) jest najmniejszy, a prawy dolny (RB) jest największym numerem, więc podane Nie (N) musi: N> = LU i N <= RB

JEŚLI N == LU i N == RB :::: Element znaleziony i przerwany zwracający pozycję / indeks Jeśli N> = LU i N <= RB = FALSE, nie ma tam No i przerywamy. Jeśli N> = LU i N <= RB = TRUE, podziel tablicę 2D na 4 równe części macierzy 2D, każda w logiczny sposób. Następnie zastosuj ten sam krok algo do wszystkich czterech pod-macierzy.

Mój algorytm jest poprawny Zaimplementowałem na komputerze znajomych. Złożoność: każde 4 porównania można wykorzystać do wyprowadzenia całkowitej liczby elementów do jednej czwartej w najgorszym przypadku. Więc moja złożoność wynosi 1 + 4 x lg (n) + 4 Ale naprawdę spodziewałem się, że to zadziała na O (n)

Wydaje mi się, że gdzieś w moich obliczeniach złożoności jest coś nie tak. Popraw, jeśli tak.

Optymalnym rozwiązaniem jest rozpoczęcie od lewego górnego rogu, który ma minimalną wartość. Poruszaj się po przekątnej w dół w prawo, aż trafisz na element, którego wartość> = wartość danego elementu. Jeśli wartość elementu jest równa wartości danego elementu, zwracana wartość jest prawdziwa.

W przeciwnym razie możemy teraz postępować na dwa sposoby.

Strategia 1:

1. Przejdź w górę w kolumnie i wyszukaj dany element, aż dojdziemy do końca. Jeśli zostanie znaleziony, zwraca znaleziony jako prawdziwy
2. Przechodzimy w lewo w rzędzie i szukamy danego elementu, aż dojdziemy do końca. Jeśli zostanie znaleziony, zwraca znaleziony jako prawdziwy
3. zwrot uznany za fałszywy

Strategia 2: Niech i oznacza indeks wiersza, a j oznacza indeks kolumny elementu przekątnego, na którym się zatrzymaliśmy. (Tutaj mamy i = j, BTW). Niech k = 1.

• Powtarzaj poniższe kroki, aż ik> = 0
  1. Szukaj, czy [ik] [j] jest równe podanemu elementowi. jeśli tak, zwrot znaleziony jako prawdziwy.
  2. Szukaj, jeśli [i] [jk] jest równe danemu elementowi. jeśli tak, zwrot znaleziony jako prawdziwy.
  3. Przyrost k

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){

    // base case for recursion
    if(minX > maxX || minY > maxY)
        return false ;
    // early fails
    // array not properly intialized
    if(arr==null || arr.length==0)
        return false ;
    // arr[0][0]> key return false
    if(arr[minX][minY]>key)
        return false ;
    // arr[maxX][maxY]<key return false
    if(arr[maxX][maxY]<key)
        return false ;
    //int temp1 = minX ;
    //int temp2 = minY ;
    int midX = (minX+maxX)/2 ;
    //if(temp1==midX){midX+=1 ;}
    int midY = (minY+maxY)/2 ;
    //if(temp2==midY){midY+=1 ;}


    // arr[midX][midY] = key ? then value found
    if(arr[midX][midY] == key)
        return true ;
    // alas ! i have to keep looking

    // arr[midX][midY] < key ? search right quad and bottom matrix ;
    if(arr[midX][midY] < key){
        if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY))
            return true ;
        // search bottom half of matrix
        if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY))
            return true ;
    }
    // arr[midX][midY] > key ? search left quad matrix ;
    else {
         return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1));
    }
    return false ;

}

Proponuję przechowywać wszystkie znaki w pliku 2D list . następnie znajdź indeks wymaganego elementu, jeśli istnieje na liście.

Jeśli nie ma, wydrukuj odpowiedni komunikat w przeciwnym razie wydrukuj wiersz i kolumnę jako:

row = (index/total_columns) i column = (index%total_columns -1)

Spowoduje to tylko binarny czas wyszukiwania na liście.

Prosimy o zgłaszanie wszelkich poprawek. :)

Jeśli rozwiązanie O (M log (N)) jest prawidłowe dla tablicy MxN -

template <size_t n>
struct MN * get(int a[][n], int k, int M, int N){
  struct MN *result = new MN;
  result->m = -1;
  result->n = -1;

  /* Do a binary search on each row since rows (and columns too) are sorted. */
  for(int i = 0; i < M; i++){
    int lo = 0; int hi = N - 1;
    while(lo <= hi){
      int mid = lo + (hi-lo)/2;
      if(k < a[i][mid]) hi = mid - 1;
      else if (k > a[i][mid]) lo = mid + 1;
      else{
        result->m = i;
        result->n = mid;
        return result;
      }
    }
  }
  return result;
}

Działające demo C ++.

Daj mi znać, jeśli to nie zadziała lub jeśli jest błąd.

Zadawałem to pytanie w wywiadach przez większą część dekady i myślę, że tylko jedna osoba była w stanie wymyślić optymalny algorytm.

Moje rozwiązanie zawsze brzmiało:

1. Przeszukaj binarnie środkową przekątną, czyli przekątną biegnącą w dół i w prawo, zawierającą element w (rows.count/2, columns.count/2).

2. Jeśli liczba docelowa zostanie znaleziona, zwraca wartość true.

3. W przeciwnym razie zostaną znalezione dwie liczby ( ui v), takie, które usą mniejsze niż cel, vsą większe niż cel i vsą jedna w prawo i jedna w dół od u.

4. Rekurencyjnie przeszukaj macierz podrzędną po prawej stronie ui na górze voraz tę na dole ui po lewej stronie v.

Uważam, że jest to ścisła poprawa w stosunku do algorytmu podanego przez Nate'a , ponieważ przeszukiwanie przekątnej często pozwala na zmniejszenie o ponad połowę przestrzeni poszukiwań (jeśli macierz jest zbliżona do kwadratu), podczas gdy przeszukiwanie wiersza lub kolumny zawsze skutkuje eliminacją dokładnie połowę.

Oto kod w (prawdopodobnie nie strasznie Swifty) Swift:

import Cocoa

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        if (matrix.isEmpty || matrix[0].isEmpty) {
            return false
        }

        return _searchMatrix(matrix, 0..<matrix.count, 0..<matrix[0].count, target)
    }

    func _searchMatrix(_ matrix: [[Int]], _ rows: Range<Int>, _ columns: Range<Int>, _ target: Int) -> Bool {
        if (rows.count == 0 || columns.count == 0) {
            return false
        }
        if (rows.count == 1) {
            return _binarySearch(matrix, rows.lowerBound, columns, target, true)
        }
        if (columns.count == 1) {
            return _binarySearch(matrix, columns.lowerBound, rows, target, false)
        }

        var lowerInflection = (-1, -1)
        var upperInflection = (Int.max, Int.max)
        var currentRows = rows
        var currentColumns = columns
        while (currentRows.count > 0 && currentColumns.count > 0 && upperInflection.0 > lowerInflection.0+1) {
            let rowMidpoint = (currentRows.upperBound + currentRows.lowerBound) / 2
            let columnMidpoint = (currentColumns.upperBound + currentColumns.lowerBound) / 2
            let value = matrix[rowMidpoint][columnMidpoint]
            if (value == target) {
                return true
            }

            if (value > target) {
                upperInflection = (rowMidpoint, columnMidpoint)
                currentRows = currentRows.lowerBound..<rowMidpoint
                currentColumns = currentColumns.lowerBound..<columnMidpoint
            } else {
                lowerInflection = (rowMidpoint, columnMidpoint)
                currentRows = rowMidpoint+1..<currentRows.upperBound
                currentColumns = columnMidpoint+1..<currentColumns.upperBound
            }
        }
        if (lowerInflection.0 == -1) {
            lowerInflection = (upperInflection.0-1, upperInflection.1-1)
        } else if (upperInflection.0 == Int.max) {
            upperInflection = (lowerInflection.0+1, lowerInflection.1+1)
        }

        return _searchMatrix(matrix, rows.lowerBound..<lowerInflection.0+1, upperInflection.1..<columns.upperBound, target) || _searchMatrix(matrix, upperInflection.0..<rows.upperBound, columns.lowerBound..<lowerInflection.1+1, target)
    }

    func _binarySearch(_ matrix: [[Int]], _ rowOrColumn: Int, _ range: Range<Int>, _ target: Int, _ searchRow : Bool) -> Bool {
        if (range.isEmpty) {
            return false
        }

        let midpoint = (range.upperBound + range.lowerBound) / 2
        let value = (searchRow ? matrix[rowOrColumn][midpoint] : matrix[midpoint][rowOrColumn])
        if (value == target) {
            return true
        }

        if (value > target) {
            return _binarySearch(matrix, rowOrColumn, range.lowerBound..<midpoint, target, searchRow)
        } else {
            return _binarySearch(matrix, rowOrColumn, midpoint+1..<range.upperBound, target, searchRow)
        }
    }
}

Biorąc pod uwagę macierz kwadratową w następujący sposób:

[abc]
[def]
[ijk]

Wiemy, że a <c, d <f, i <k. Nie wiemy, czy d <c lub d> c itd. Gwarancje mamy tylko w 1 wymiarze.

Patrząc na elementy końcowe (c, f, k), możemy zrobić coś w rodzaju filtra: czy N <c? szukaj (): następny (). W ten sposób mamy n iteracji w wierszach, przy czym każdy wiersz przyjmuje albo O (log (n)) dla wyszukiwania binarnego, albo O (1), jeśli zostanie odfiltrowany.

Podam PRZYKŁAD, gdzie N = j,

1) Sprawdź wiersz 1. j <c? (nie, przejdź dalej)

2) Sprawdź wiersz 2. j <f? (tak, wyszukiwanie binariów nic nie daje)

3) Sprawdź wiersz 3. j <k? (tak, funkcja wyszukiwania binariów znajduje to)

Spróbuj ponownie z N = q,

1) Sprawdź wiersz 1. q <c? (nie, przejdź dalej)

2) Sprawdź wiersz 2. q <f? (nie, przejdź dalej)

3) Sprawdź wiersz 3. q <k? (nie, przejdź dalej)

Prawdopodobnie istnieje lepsze rozwiązanie, ale łatwo to wyjaśnić .. :)

Ponieważ jest to pytanie do wywiadu, wydaje się, że prowadzi ono do dyskusji na temat programowania równoległego i redukcji map algorytmów .

Zobacz http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html