> On 2013-10-24 11:29, Blaicher, Christopher Y. wrote:
>> ...
>> The second method used a binary chop of the data then scanned for
the next entry. It was ugly, but it did its job. There are lots of
limitations to it.
>>
> Somewhat elliptical. I assume he means that from any point
> in the table, which may be in the interior of an entry of
> a priori unknown length, there's a method for locating the
> beginning and end of that entry, perhaps a reserved character
> such as BLANK, NUL, LF, ...
>
> I think that should be feasible.
>
> -- gil
Yep, but so ugly. :-) And, so slow.
The math people would have to figure it out for sure, but I would almost
bet that such logic that Chris suggested would only be faster than a
linear search if the table is very large and the rows very short.
Tony Thigpen
-----Original Message -----
From: Paul Gilmartin
Sent: 10/24/2013 06:00 PM
On 2013-10-24 15:51, John Gilmore wrote:
Tony writes that you just can't binary search a variable length table,
and this is certainly true if what he means is that you cannot search
a table the length of which changes while you are searching it.
You can, however, search a table that varies in length on different
occasions. How not?
I understand he meant a table containing entries of nonuniform lengths.
On 2013-10-24 15:43, Tony Thigpen wrote:> After a couple of posts about my
post, I will go back to my point.
...
You just can't binary search a variable length table.
Perhaps ...
On 2013-10-24 11:29, Blaicher, Christopher Y. wrote:
...
The second method used a binary chop of the data then scanned for the next
entry. It was ugly, but it did its job. There are lots of limitations to it.
Somewhat elliptical. I assume he means that from any point
in the table, which may be in the interior of an entry of
a priori unknown length, there's a method for locating the
beginning and end of that entry, perhaps a reserved character
such as BLANK, NUL, LF, ...
I think that should be feasible.
-- gil
