二維數組中的二進制搜索

我想知道，可以二分查找應用於一個二維數組？二維數組中的二進制搜索

條件上的數組是什麼？排序在2D？
會是什麼時候複雜度它？
算法如何改變搜索的邊界（minX，maxX，minY，maxY）？

編輯：

一維二進制搜索維持2個指針minX和maxX .. 它選擇中間指數(minX+maxX)/2並將其與搜索值進行比較，如果大於改變maxX，其他變化minX .. 。直到minX>=maxX

僞正常的二進制代碼seacrh：

min := 1; 
    max := N; {array size: var A : array [1..N] of integer} 
    repeat 
    mid := min + (max - min) div 2; 
    if x > A[mid] then 
     min := mid + 1 
    else 
     max := mid - 1; 
    until (A[mid] = x) or (min > max);

謝謝

來源

2010-12-12 Betamoo

有什麼特別的你想要實現？ – NPE 2010-12-13 14:53:24

我的第一個建議是讓你的一維算法得到解決。可能有幾個界限問題。考慮一個大小爲1的數組。這裏'min = 1'和'max = 1'。然後'mid：= min +（max-min）div 2'產生'mid = 0'（假設整數運算）。然後誰知道'A [mid]'等於什麼（給定'A'被索引爲：1..N）。 – NealB 2010-12-13 16:23:26

@NealB這只是維基百科中的代碼...它並不重要，它只是爲了演示.. – Betamoo 2010-12-14 12:45:41

二進制搜索要求您的數組排序。反過來，排序需要數組元素上的總體排序關係。在1-D中很容易理解這意味着什麼。我認爲你必須在你的二維數組中定義一維索引，並確保數組元素是沿着該索引排序的。

您有多種一維索引方案可供選擇，基本上可以使用任何空間填充曲線。想到的最明顯的是：

從第一個元素開始，沿着每一行讀取，在每一行的末尾轉到下一行的第一個元素。
同樣，逐行替換。
對角化，您可以依次讀取每個對角線。

贊@Bart Kiers，我不明白你的第二點。

來源

2010-12-12 12:13:40

請看看修改後的問題.. – Betamoo 2010-12-12 13:22:57

我看着修改後的問題。現在我不明白的是第三不是第二。 – 2010-12-12 14:53:36

我想過這個問題，去年...所以，我會選用這種方法：

考慮你的二維數組表示在平面上的點。例如，你的元素A [i] [j]表示一個x = i和y = j的點。在飛機上使用二進制搜索我有點所有使用這個情況分：

點P1 < P2當且僅當：

（x座標P1）的<（P2的x座標）
（x座標p1的）=（P2的x座標）和（P1的y座標）<（p2的Y座標）

Othwerwise P1> P2 =。

現在，如果我們查看我們的2D數組，第二行中的元素應該大於第一行中的元素。在通常排序的相同行元素中（根據其列號）。

換句話說：

A [i] [j]> A [k]的[j]的當且僅當（ⅰ> K）。（在不同的行和列中）
A [i] [j]> A [i] [k]當且僅當（j> k）。（在同一行和不同列中）

考慮你的數組有N行和M列。

for i:=0 to N-1 do 
    for j:=0 to M-1 do 
     T[i*N + j]:= A[i][j];

現在你有一維數組： - 現在，你應該（即暫時）使用此公式（臨時陣列T）將您的二維數組一維數組。以通常的方式分類。現在您可以使用簡單的二進制搜索算法進行搜索。

或者您可以使用此公式將您的排序陣列回二維數組：

for i:=0 to N*M-1 do 
    A[i div N][i - (i div N)*N]:= T[i];

並使用兩個二進制搜索：

一個被搜索的x座標（在我們的意思行）另一個由y座標（在我們的意義上的列）爲同一行中的元素。

換句話說，當你計算mid = mid + (max - min) div 2，你可以比較元素A [MID] [0]與您的關鍵元素（在你的代碼有X名稱），當你發現你的牙齒列，你可以調用此行中的另一個二分搜索（A [mid]中的二分搜索）。

複雜度的兩種方法：

用於trasformed陣列簡單二進制搜索：用於2D陣列的兩個二進制搜索日誌（N * M）
：日誌（N）爲外搜索（按行） + log（M）用於內部搜索（按列）。

使用對數函數的性質，我們可以簡化最後一個表達式：日誌（N）+日誌（M）=日誌（N * M）。

所以，我們證明，這兩種方法具有相同的複雜性，並不重要，哪一個使用。但是，如果對你不難，我建議你簡單地將你的數組轉換爲1-D，並使用簡單的二進制搜索（它非常簡單，易於調試和檢查）。

來源

2010-12-12 14:25:32 Ilnur

我在O(m + n)時間複雜度，其中m = no，以簡單的方式解決它。行和n = no。列。

的算法很簡單：我從右上角開始（我們也可以從左下角開始），並向左移動，如果當前元素大於被搜索和底部如果該值當前元素小於要搜索的值。

Java代碼是這樣的：

public static int[] linearSearch(int[][] a, int value) { 
    int i = 0, j = a[0].length - 1; // start from top right corner 

    while (i < a.length && j >= 0) { 
     if (a[i][j] == value) { 
      return new int[]{i, j}; 
     } else if (a[i][j] > value) { 
      j--; // move left 
     } else { 
      i++; // move down 
     } 
    } 
    // element not found 
    return new int[]{-1, -1}; 

}

Gist

您可以進一步通過使用一種叫做Improved Binary Partition方法降低了時間複雜度。

來源

2015-08-25 10:03:07

您可以將二維數組轉換爲一維數組並在此處執行二分查找。 mxn陣列的複雜度爲O(log(m * n))。

來源

2017-03-30 00:22:23

二維數組中的二進制搜索

回答

相關問題