二维阵列上的二进制搜索
问题描述:
我有一个完全排序的二维数组。下面的阵列例子二维阵列上的二进制搜索
1 2 3
5 6 7
9 10 11
和
1 2 3 4 5
6 7 8 9 10
我想用这些阵列上二进制搜索。让rows
是行数和成为cols
列
最初start = 0
和end = rows * cols -1
在上面的3×3阵列的数量,中点工程以有四个[9个元素。现在我该如何找出中点对应的行和列?有没有任何标准公式?
答
的公式是非常简单的:
row = number/cols_per_row;
col = number%cols_per_row;
答
让size = rows * cols
mid = size // 2
(整数除法)
row = mid // cols
col = mid % cols
(其余为整数除法)
嗯..只是好奇,你是怎么想到的? – vinoth 2013-02-27 10:09:15
对于每一个cols_per_row数字,你走一排。所以这解释了为什么使用这个公式找到第一个数字,对吗?至于第二个 - 你所在的列是循环重复每个cols_per_row数字,所以'%'描述了这样的行为,对吧? – 2013-02-27 10:12:03
什么是'cols_per_row'? – 2013-02-27 10:16:25