java - 在具有重复Java的二维数组中进行二进制搜索

Question

设计一个算法，FindElement(a,p)，其中“a”是正整数重复的二维方阵，每行整数按非降序排列: a[i][0] ≤ a[i][1] ≤ a[i][2] · · · ≤ a[i][n-1](i=0,1,...,n-1),.该算法应定义 p 是否包含在 a 中。如果“p”成立，它应该返回 true，否则返回 false。您的算法必须尽可能高效。算法应该基于二分查找

我找到了以下解决方案(但我不确定它是否正确):

解决方案是使用二进制搜索一次搜索在一行上工作的元素。二进制搜索大小为 (n) 的给定排序行需要 O(Log(n))，因此在最坏的情况下搜索整个数组需要 O(nlog(n))。

这个解决方案是否适合给定的任务？我不知道如何实现这个算法，请你给我伪代码或解释如何去做。提前致谢。

Answer 1

是的，您的解决方案似乎正确且有效(鉴于您对初始问题的描述，他们可能希望您使用二进制搜索)。你的算法应该是这样的:

public Point FindElement(int[][] matrix, int number) {
    Point p = new Point(); // holds two integers and represents 
                           // a position in the matrix.
    int found = -1;
    for(int i = 0; i < N; i++) {
        found = binarySearch(matrix[i], number, 0, N);
        if(found != -1) { 
           p.setX(i); 
           p.setY(found); 
           return p; 
        }
    }
    return null;
}

可以根据此处找到的伪代码实现二进制搜索:http://en.wikipedia.org/wiki/Binary_search_algorithm#Recursive