在Lua中对数组中的数组进行二分查找

2013-10-22 15:56:47
收藏：0
阅读：129
评论：1

我从记忆中的 Python 中编写了一个 Lua 二分查找函数，它可用于单个数组（表）。

    function bisect_left(a, x, lo, hi)
        lo = lo or 1
        hi = hi or nil
        if lo < 0 then
            error('lo must be non-negative')
        end
        if hi == nil then
            hi = #a
        end
        while lo < hi do
            mid = math.floor((lo+hi) / 2)
            if a[mid] < x then
                lo = mid+1
            else
                hi = mid
            end
        end
        return lo
     end

但是，我遇到了需要搜索排序后的数组（表）（表的表）。它们通过索引 1 进行排序

squares = {{300, 400, 123456, 9}, {400, 500, 323456, 9}, {420, 610, 5123456, 9}, {530, 700, 8123456, 9}, {840, 960, 9123456, 1}}

在 Python 中，我会做类似于重载比较运算符 cmp 的操作，如

Class overload(object):
    def __init__(self, value, index):
        self.value = value
        self.index = index
    def __cmp__(self, other):
        return cmp(self.value, other[self.index])

这在 Lua 中最快的方法是什么？我能想到（我认为）缓慢的方法，但是我的函数式编程经验让我想知道是否有我无法猜测的方法。

点赞
用户752976
用户752976

首先，看看第一个例子中的比较器是什么。让我们看一下一个简单的行：

if lo < 0 then

这可以写成以下形式：

if numericCompare(lo, 0) then

numericCompare 明显是 function numericCompare(a,b) return a < b end。

那么，将所有比较都更改为您可能称为 tableCompare 的内容，并实现该比较器，推测为

function tableCompare(a,b)
    return a[1] < b[1]
end

通常，由于 Lua 表的本质，tab[1] 访问应该相当快速。先编写代码，进行分析，然后再尝试进行优化。

您可以在 Lua 中重载运算符，但是在这种情况下，我认为以比较器为参数，并明确命名，稍微更易于阅读。

2013-10-22 15:57:30

作者:

用户411929

用户411929
推荐文章