2 ms·
(Slightly off topic, but maybe still interesting.) I used to write binary searches like yours, with two tests per iteration: while lo < hi: mid = (
by garethrees 10y ago
(Slightly off topic, but maybe still interesting.) I used to write binary searches like yours, with two tests per iteration:
while lo < hi:
mid = (lo + hi) // 2
if a[mid] == x:
return mid
elif a[mid] < x:
lo = mid + 1
else:
hi = mid
return -1
But then I discovered that there's an alternative approach which has only one test per iteration:
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
if lo < len(a) and a[lo] == x:
return lo
else:
return -1
If comparisons are expensive compared to other operations then this is twice as fast as the variant with two comparisons per iteration. (If comparisons are cheap, as they are if you are searching an array of numbers in a compiled language, then it doesn't make much difference.)