使用二进制搜索在已排序的多维数组中查找数字

Question

我们得到了一个增加排序的多维数组,例如:

int[][] mat = {{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}};

如何使用二进制搜索查找特定数字？让我说我正在寻找3.

Answer 1

您可以通过将一维索引转换为二维对应来完成此操作.例如,索引0映射到0, 0,但索引4将映射到1, 0,索引15将映射到3, 3.

这样您就可以使用标准的二进制搜索算法,当您需要在该特定索引处查找值时,您所要做的就是调用转换函数.

将一维索引转换为二维对应的公式为:

row = floor(index / columns);
column = index % columns;

这假设每个数组都已排序,并且在展平时,结果数组也会排序.