75% speedup for zdump on 64-bit Solaris sparc

[Paul Eggert]

The following change to localtime.c sped up "zdump -v
America/Los_Angeles" by 75% on my host (Solaris sparc, 64-bit,
compiled with gcc 4.0.2 -m64).  It substitutes a binary earch for a
linear one.  (I resisted the temptation to do a linear interpolation
search. :-)

Though this is a win, I'm a bit puzzled by why sp->timecnt was so
large for "America/Los_Angeles".  sp->timecnt was 1200, but
America/Los_Angeles contains nowhere near 1200 transitions.  There
might be an even bigger performance win if the number of transitions
were shrunk in memory, down to the minimum number needed to represent
the data.

--- localtime.c	2006/02/22 00:24:05	2006.2.0.2
+++ localtime.c	2006/02/24 07:09:27	2006.2.0.3
@@ -1266,9 +1266,17 @@ struct tm * const	tmp;
 				break;
 			}
 	} else {
-		for (i = 1; i < sp->timecnt; ++i)
-			if (t < sp->ats[i])
+		int lo = 1;
+		int hi = sp->timecnt;
+		for (;;) {
+			i = (lo + hi) >> 1;
+			if (hi <= lo)
 				break;
+			if (t < sp->ats[i])
+				hi = i;
+			else
+				lo = i + 1;
+		}
 		i = (int) sp->types[i - 1];
 	}
 	ttisp = &sp->ttis[i];