Lua插值查找：均匀分布的进阶查找

-- 错误：均匀分布也固定对半，白多走几轮
local mid = math.floor((lo + hi) / 2)

local function interpSearch(a, target)
    local lo, hi = 1, #a
    while lo <= hi
        and target >= a[lo] and target <= a[hi] do
        if a[lo] == a[hi] then
            return a[lo] == target and lo or 0
        end
        local pos = lo + math.floor(
            (target - a[lo]) / (a[hi] - a[lo])
            * (hi - lo))
        if a[pos] == target then
            return pos
        elseif a[pos] < target then
            lo = pos + 1
        else
            hi = pos - 1
        end
    end
    return 0
end