gpt4 book ai didi

algorithm - 二维数组中的二进制搜索

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:08:22 27 4
gpt4 key购买 nike

我想知道,二进制搜索可以应用于二维数组吗?

  • 数组的条件是什么?按二维排序??
  • 它的复杂度时间是多少?
  • 算法将如何改变搜索边界 (minX,maxX,minY,maxY) ??

编辑:

一维二进制搜索维护 2 个指针 minXmaxX..它选择中间索引 (minX+maxX)/2 并将其与搜索值进行比较,如果大于则更改 maxX,否则更改 minX ...直到 minX>=maxX

普通二进制seacrh的伪代码:

 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 = 没有。列数

The algorithm is simple: I started from top right corner (we can also start from bottom left corner) and move left if current element is greater than the value to be searched and bottom if current element is smaller than the value to be searched.

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};

}

Gist

您可以使用称为 Improved Binary Partition 的方法进一步降低时间复杂度.

关于algorithm - 二维数组中的二进制搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4421479/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com