C++ : Fast searching in 2d array

Question

我有一个 2D 数组，我按以下方式在我的代码中使用它:

搜索特定条目需要很多时间，而我想减少搜索元素的时间。谁能建议我可以做哪些优化来减少在此二维数组中搜索的时间？

 for( counter1=0; counter1< size ; ++counter1)
    {   
    int index= GVector[counter1];
    SingleTableEntries NewNextState=NewSingleTable[Next][index];

    Next=NewNextState.Next_State;
    if(NewNextState.accept1==1 )
    {
        return 1;           
    }

    index= GuideVector[counter1+1];

    NewNextState=NewSingleTable[Next][index];

    NextState_chunk2=NewNextState.Next_State;
    if(NewNextState.accept1==1 )
    {
        return 1;       
    }       
    //code
 }

Answer 1

给定一个 n x n 矩阵，其中每一行和每一列都按递增顺序排序。给定一个数字x，如何判断这个x是否在矩阵中。设计的算法应具有线性时间复杂度。

1. 从右上角的元素开始
2. 循环:比较这个元素 e 和 x i) 如果它们相等则返回它的位置 ii) e < x 然后将其向下移动(如果超出矩阵范围则 break 返回 false) iii) e > x 然后将其向左移动(如果超出矩阵范围则 break 返回 false)
3. 重复 i)、ii) 和 iii) 直到找到元素或返回 false

下面的函数在 mat[][] 中搜索元素 x。如果找到该元素，则打印其位置并返回 true，否则打印“未找到”并返回 false。

int search(int mat[4][4], int n, int x) {
    int i = 0, j = n-1;  //set indexes for top right element
    while ( i < n && j >= 0 ) {
        if ( mat[i][j] == x ) {
            printf("\n Found at %d, %d", i, j);
            return 1;
        }
        if ( mat[i][j] > x )
        j--;
        else //  if mat[i][j] < x
        i++;
    }
    printf("\n Element not found");
    return 0;  // if ( i==n || j== -1 )
}

int main() {
    int mat[4][4] = {   {10, 20, 30, 40},
                        {15, 25, 35, 45},
                        {27, 29, 37, 48},
                        {32, 33, 39, 50},
                    };
    search(mat, 4, 29);
    getchar();
    return 0;
}

时间复杂度:O(n)

上述方法也适用于 m x n 矩阵(不仅适用于 n x n)。复杂度为 O(m + n)。