在这种情况下，我如何以最有效的方式在数组中找到一个值？

Question

注意：这个算法应该以最有效的方式完成，这是一个坏主意 O(n^2)

这是一个二维数组，现在请注意，乍一看很难看出，但该数组上有一个隐藏的图案。

这个数组实际上是排序的，看看下面的图片，您现在可能会看到规律。

这里的目标是创建一个函数来搜索数组中的值，该数组遵循我在图像中向您展示的确切模式，您需要 return true 如果值是 found 并且 print 值 所在的列和行 在数组中。如果未找到值 return false

这里有一个例子

这里是函数签名

public static boolean search(int [][]mat,int num){
    //Code Here
}

假设我们正在该数组中查找值 22（图像中的相同数组）

int [][]arr= {{1,3,7,9},{6,4,15,11},{36,50,21,22},{60,55,30,26}}
search(arr,22); //Returns true and also will be printed "row = 2 col = 3"

search(arr,86); //Returns false

Answer 1

矩阵中的索引 i 和 j 可以从 0 到 15 范围内的单个线性索引计算得出。这将允许您进行正常的二进制搜索，只需将每个索引从一维到二维。

private static int i(int index) {
    return iBit(index / 4) * 2 + iBit(index % 4);
}

private static int iBit(int part) {
    return (part / 2) ^ (part % 2);
}

private static int j(int index) {
    int temp = index / 2;
    return temp / 4 * 2 + temp % 2;
}

有点棘手。因此，让我们检查这些方法是否有效：

    for (int index = 0; index < 16; index++) {
        System.out.format("%2d -> %d %d%n", index, i(index), j(index));
    }

输出：

 0 -> 0 0
 1 -> 1 0
 2 -> 1 1
 3 -> 0 1
 4 -> 2 0
 5 -> 3 0
 6 -> 3 1
 7 -> 2 1
 8 -> 2 2
 9 -> 3 2
10 -> 3 3
11 -> 2 3
12 -> 0 2
13 -> 1 2
14 -> 1 3
15 -> 0 3

数字与问题中的模式一致。

NOTE: this algorithm should be done in the most efficient way that's a bad idea to have O(n^2)

真是废话。 Big-O 是根据输入大小向无穷大增长时的行为定义的。 16 不会增长到无穷大。 4也不是。当矩阵大小不变时，即使是简单的线性搜索也是O(1)。

在这种情况下，我如何以最有效的方式在数组中找到一个值？

How do i find a value in an array in the most efficient way in that case?

java

arrays

algorithm

array-algorithms