[tyndur-devel] [PATCH 1/2] libc: Binäresuche für bsearch
Andreas Freimuth ·
* libc/bsearch: sucht jetzt binär Signed-off-by: Andreas Freimuth <m.nemo at gmx.net> --- src/lib/stdlibc/bsearch.c | 22 ++++++++++++++-------- 1 files changed, 14 insertions(+), 8 deletions(-) diff --git a/src/lib/stdlibc/bsearch.c b/src/lib/stdlibc/bsearch.c index ef64eda..39f0a9c 100644 --- a/src/lib/stdlibc/bsearch.c +++ b/src/lib/stdlibc/bsearch.c @@ -50,18 +50,24 @@ void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)) { - size_t i; const void* obj; - // FIXME Binaer suchen ginge schneller... + if (nel == 0) { + return NULL; + } + + obj = base + (width * (nel >> 1)); + int cmp = compar(key, obj); - for (i = 0; i < nel; i++) { - obj = base + (width * i); - if (compar(key, obj) == 0) { - return (void*) obj; + if (cmp == 0) { + return (void*)obj; + } else if (cmp < 0) { + if (nel >> 1 == 0) { + return NULL; } + return bsearch(key, base, nel - (nel >> 1), width, compar); + } else { + return bsearch(key, obj + width, nel - (nel >> 1) - 1, width, compar); } - - return NULL; } -- 1.7.6.4
Antworten
- [tyndur-devel] [PATCH 2/2] tests: Test für bsearch · Andreas Freimuth
- [tyndur-devel] [PATCH 1/2] libc: Binäresuche für bsearch · Kevin Wolf