我想知道，二进制搜索可以应用于2D阵列吗？
编辑：
1D上的二进制搜索保持2个指针minX和maxX ..它选择中间索引(minX+maxX)/2并将其与搜索值进行比较，如果更大则更改maxX，否则更改minX ...直到minX>=maxX
用于普通二进制搜索的伪代码：
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);
谢谢
我在O(m + n)时间复杂度中以一种简单的方式解决了它，其中m = no。行和n =否。列。
算法很简单：我从右上角开始（我们也可以从左下角开始），如果当前元素大于要搜索的值，则向左移动;如果当前元素小于要搜索的值，则向下移动。
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};
}
您可以使用名为Improved Binary Partition的方法进一步降低时间复杂度。
去年我想到了这个问题......所以，我选择了这种方法：
考虑您的2D数组表示平面中的点。例如，元素A [i] [j]表示x = i且y = j的点。要在飞机上使用二分搜索，我使用以下条件对所有点进行排序：
点p1 <p2当且仅当：
否则p1> = p2。
现在，如果我们查看2D数组，第2行中的元素应该大于第1行中的元素。在通常排序的相同行元素中（根据其列号）。
换句话说：
考虑你的数组有N行和M列。现在你应该（临时）使用这个公式（T - 临时数组）将你的2D数组转换为1D数组：
for i:=0 to N-1 do
for j:=0 to M-1 do
T[i*N + j]:= A[i][j];
现在你有1D阵列。按常规方式排序。现在您可以使用简单的二进制搜索算法进行搜索。
或者，您可以使用以下公式将已排序的数组转换回2D数组：
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]与你的key-element（在你的代码中它有x名称）进行比较，当你找到你的元素的行时，你可以调用另一个二进制搜索这一行（A [mid]中的二进制搜索）。
两种方法的复杂性：
使用对数函数的属性，我们可以简化最后的表达式：log（N）+ log（M）= log（N * M）。
因此，我们证明了两种方法都具有相同的复杂性并且无关紧要，哪种方法可以使用。
但是，如果你不难，我建议你简单地将你的数组转换为1-D并使用简单的二进制搜索（它非常简单，易于调试和检查）。
二元搜索以分而治之的方式工作，
int r = arr.length; // ROW Count
int c = arr[0].length; // Column Count
int start = 0; // Initialize with the 0
int end = r*c-1; // Last Index
我们将继续迭代while循环，每次我们根据需要更新开始和结束索引。 while（start <= end）{
int mid = (start+end)/2;
int midX = mid/c;
int midY = mid%c;
如果当前值等于search元素，那么我们只需要打印并返回它。
if(arr[midX][midY] == searchElement){
return true;
}
如果当前值小于搜索元素，那么我们只需要将mid值更新为mid = mid + 1
if(arr[midX][midY] < searchElement){
start = mid+1;
}
如果当前值大于搜索元素，那么我们只需要将mid值更新为mid = mid - 1
else{
end = mid-1;
}
二进制搜索要求对数组进行排序。反过来，排序需要数组元素的总排序关系。在一维中，很容易理解这意味着什么。我认为您必须在二维数组中定义一维索引，并确保数组元素沿该索引排序。
您有多种一维索引方案可供选择，基本上任何空间填充曲线都可以。想到的显而易见的是：
就像@Bart Kiers一样，我不明白你的第二点。
您可以将2D数组转换为1D数组并在此处进行二进制搜索。 O(log(m * n))阵列的复杂性是mxn。