function FindLowestAndHighest (myTable)
local lowest, highest
for k in pairs(myTable) do
if type(k) == "number" and k % 1 == 0 and k > 0 then -- Assuming mixed (possibly non-integer) keys
if lowest then
lowest = math.min(lowest, k)
highest = math.max(highest, k)
lowest, highest = k, k
return lowest or 0, highest or 0 -- "or 0" in case there were no indices
Untested, but something like the above would be needed in the most generic case. pairs() isn't particularly fast, and in the absence of any context you'll have to iterate the entire table anyhow, since there's no guaranteed order in how the keys are distributed.
table.maxn() gives you the highest index, but any speed gain comes from the compiler, not because it somehow got around those algorithmic constraints. (http://www.lua.org/source/5.1/ltablib.c.html#maxn, basically the same code minus the integer check)
If you know your maximum upper bound and it's fairly low, then a straight-up iteration is probably fine. There's going to be some crossing-over point versus pairs() for a truly sparse table, which can be found by experiment.
Another option might be to fill "empty" elements with false or some dummy "nil" table you can compare against and ignore. Then you can at least search reliably in [1, #myTable], and Lua will maintain the (faster) integer hash structure internally. Your users (and in your own case, your serialization library) may need to be aware of this, obviously.
If you need something more heavy-duty, it's on to the world of data structures. (Probably something like an "ordered map".)