> ----- Original Message ----- > > From: "Dougie Lawson" <[email protected]> > To: [email protected] > Sent: Monday, October 21, 2013 6:32:15 AM > Subject: Linear search vs binary > > If I have a table of 3,500 entries of twelve bytes (I'm doing a compare of > eight bytes to find the entry I'm looking for and a check on a half word > marker for the end of the table to avoid running off the end) then is it > worth the pain of re-writing it as a binary search. > > If it is worth the pain and does anyone have a sample binary search tucked > away. > > The table is built into a CSECT at the bottom of my code. I can restructure > it if we need any special pointers to make a binary search work. > You need at least a pointer to the end of the table. Otherwise, the preliminary scan for the end marker costs twice as much as doing a linear search, on the average.
And the table needs to be sorted, but only once. Unless there are dynamic insertions and deletions. If these are frequent, a tree structure might be preferable. -- gil
