From 3d8322c7ad659210a4c8770ef455ca729ce7f395 Mon Sep 17 00:00:00 2001 From: Fangrui Song Date: Sat, 21 Jul 2018 17:34:00 -0700 Subject: [PATCH] bsearch: simplify and optimize maintainer's note: the key observation here is that the compared element is the first slot of the second ceil(half) of the array, and thus can be removed for further comparison when it does not match, so that we descend into the second ceil(half)-1 rather than ceil(half) elements. this change ensures that nel strictly decreases with each iteration, so that the case of != but nel==1 does not need to be special-cased anymore. --- src/stdlib/bsearch.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/src/stdlib/bsearch.c b/src/stdlib/bsearch.c index 61d89367..fe050ea3 100644 --- a/src/stdlib/bsearch.c +++ b/src/stdlib/bsearch.c @@ -7,13 +7,13 @@ void *bsearch(const void *key, const void *base, size_t nel, size_t width, int ( while (nel > 0) { try = (char *)base + width*(nel/2); sign = cmp(key, try); - if (!sign) return try; - else if (nel == 1) break; - else if (sign < 0) + if (sign < 0) { nel /= 2; - else { - base = try; - nel -= nel/2; + } else if (sign > 0) { + base = (char *)try + width; + nel -= nel/2+1; + } else { + return try; } } return NULL; -- 2.25.1