二维数组中的二进制搜索与重复的Java
设计一个算法FindElement(a，p)，其中"a“是有重复的正整数的二维正方形数组，每一行整数都是非降序的: ai≤ai≤ai···≤ai (ai，.。.，n-1)，.算法应该定义p是否包含在a中。如果"p“是成立的，它应该返回true，否则返回false。你的算法必须尽可能的高效。算法应基于二进制搜索
我找到了以下解决方案(但我不确定它是否正确)：
解决方案是使用二进制搜索一次搜索一行上工作的元素。对给定大小为(n)的排序行进行二进制搜索需要O(Log(n))，因此在最坏的情况下，搜索整个数组需要O(nlog(n))。
这个解决方案是否适用于给定的任务？我不知道如何实现这个算法，请你给我伪代码或解释如何做。提前谢谢。
回答 6
Stack Overflow用户
发布于 2011-11-23 07:05:09
是的，您的解决方案看起来是正确和有效的(根据您对初始问题的描述，他们可能希望您使用二进制搜索)。你的算法应该是这样的：
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
Stack Overflow用户
发布于 2011-11-23 07:08:08
是的，解决方案是正确的。
下面是伪代码
int index = -1;
for (int i : height of array){
int[] putIn1Darray = a[i][j] where j = 0 to n;
index = Arrays.binarySearch(putIn1Darray,p);
if (index == -1)
//Element not found yet
continue;
else
//Element found
break;
}
print index;上面的算法用于显示元素p的第一个匹配项。
您可以根据您的硬件进行修改。
Stack Overflow用户
发布于 2011-11-23 07:07:28
二进制搜索只适用于排序列表。因此，如果它是合适的:我会说是。只要确保你在得到答案时向前和向后一步，就可以得到所有的副本。
您可以使用以下内容作为基础：http://www.java-tips.org/java-se-tips/java.lang/binary-search-implementation-in-java.html
https://stackoverflow.com/questions/8234915
复制相似问题
腾讯云开发者
