按行和明智排序的矩陣搜索

Question

我們有一個n×n矩陣，其中每行和每列按升序排列。

給出一個數字x，如何判斷這個x是否在矩陣中，好於O（n）的複雜度？

Answer 1

我認爲只是使用二進制搜索。

二進制搜索的時間複雜度爲O（log（n））。因此，在n×n矩陣的情況下，時間複雜度爲O（log（n^2））= O（2log（n））。

它比O（n）好。

-----（編輯）/這是我的cpp代碼。

#include<vector> 
#include<iostream> 
#include<cstdio> 

using namespace std; 

int n = 10; 
vector<vector<int> > arr; 
int search_cnt; 

int _1to2(int x) 
{ 
    int row, col; 

    row = (x - 1)/n + 1; 
    if(x % n == 0) 
     col = n; 
    else 
     col = x % n; 

    return arr[row][col]; 
} 

int _2to1(int row, int col) 
{ 
    return (row - 1) * n + col; 
} 

int binary(int find) 
{ 
    int low = 1, high = n*n, mid; 

    while(low <= high) 
    { 
     search_cnt++; 
     mid = (low + high)/2; 
     if(_1to2(mid) > find) 
      high = mid - 1; 
     else if(_1to2(mid) < find) 
      low = mid + 1; 
     else 
     { 
      printf("search_cnt = %d, ", search_cnt); 
      return mid; 
     } 
    } 

    return -1; 
} 

int main() 
{ 
    int cnt = 1; 
    search_cnt = 0; 

    arr.resize(n+1); 
    for(int i = 0; i <= n; i++) 
     arr[i].resize(n+1); 

    for(int i = 1; i <= n; i++) 
     for(int j = 1; j <= n; j++) 
      arr[i][j] = cnt++; 

    for(int i = 1; i <= n*n; i++) 
    { 
     printf("searching pos = %d \n", binary(i)); 
     search_cnt = 0; 
    } 

    return 0; 
}