使用二分搜索在已排序的多维数组中查找数字 [英] Find a number in sorted multidimentional array with binary search

问题描述

我们有一个增加排序的多维数组，例如：

we got an increasing sorted multidimensional array for example:

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

如何使用二元搜索来查找特定数字？让我说我正在寻找3。

How can I use binary search to find a specific number? let's say im looking for 3.

推荐答案

你可以通过将一维索引转换为二维对应物来实现。例如，index 0 映射到 0,0 ，但索引 4 将映射到 1,0 ，而索引 15 将映射到 3， 3 。

You can do this by translating the one-dimensional index into its two-dimensional counterpart. For example, index 0 maps to 0, 0, but index 4 will map to 1, 0, and index 15 will map to 3, 3.

这种方式你可以使用标准的二进制搜索算法，你所要做的就是调用翻译函数需要查找该特定指数的值。

This way you can use the standard binary-search algorithm, and all you have to do is to invoke the translation function when you need to look up the value at that particular index.

将一维指数转换为二维指数的公式为：

The formula to translate the one-dimensional index into its two-dimensional counterpart would be:

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

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

This assumes that each array is sorted and that when flattened, the resulting array is also sorted.

这篇关于使用二分搜索在已排序的多维数组中查找数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！