Reuse, not rework
Home

License Awareness



Highly Reusable Software

By activity
Professions, Sciences, Humanities, Business, ...

User Interface
Text-based, GUI, Audio, Video, Keyboards, Mouse, Images,...

Text Strings
Conversions, tests, processing, manipulation,...

Math
Integer, Floating point, Matrix, Statistics, Boolean, ...

Processing
Algorithms, Memory, Process control, Debugging, ...

Stored Data
Data storage, Integrity, Encryption, Compression, ...

Communications
Networks, protocols, Interprocess, Remote, Client Server, ...

Hard World
Timing, Calendar and Clock, Audio, Video, Printer, Controls...

File System
Management, Filtering, File & Directory access, Viewers, ...


NAME

librock_ITERbinsearch - implement binary search of indexed, ordered list
#License - #Source code - #Example Use -

SYNOPSIS

#include <librock/procede.h>

int librock_ITERbinsearch(
        long *pLow, /* Low side */
        long *pHigh, /* High side */
        long side);

DESCRIPTION

This performs the manipulatation of indexes needed during a binary search of an integer indexed, ordered list. On each call, it reduces the difference between a low and high index based on the result of a comparison the caller made with (*pLow + *pHigh)/2. One of the indexes is moved towards the other.

The item at (*pHigh on the initial call) will never be checked. After the initial call, and until the return is 0, *pLow and *pHigh should not be adjusted or used by the caller, except to calculate (*pLow + *pHigh)/2.

If there are multiple entries of the same value, the first entry in the list will be found.

Returns non-zero if more iterations are needed.

When finished, the result in *pHigh and *pLow are as follows:

    *pLow == *pHigh if the item was found exactly.  This will
            be the first item that matches if there are multiple
            identical matches.

    *pHigh = *pLow+1 if item was not found.  *pLow is before
            the item, *pHigh is after.  Note that *pHigh might be
            unchanged from the first call, so it may point off the
            end of the list.

    *pHigh == *pLow-1.  if the list is empty (i.e. no entries found)

Note that *pLow might be > *pHigh during iteration, but not when
return value is 0.  (This is part of how multiple identical
matches are handled.)

Typical Use:

#ifdef librock_TYPICAL_USE_ITERbinsearch
    char *item[10] = {
        "a","b","c","d","e","find this","find this","h","i","j"
    };
    char *tolocate = "find this";
    long itest;
    long low = 0;
    long high = 10;
    int side;

    do {
            itest = (high+low)/2;
            side = strcmp(tolocate,item[itest]);
    } while(librock_ITERbinsearch(&low,&high,side));
    if (low == high) {
        printf("Found at %d\n",low);
    } else if (high == low+1) {
        printf("Not found.  Insert after %d.  Before %d\n",low,high);
    }
#endif

USES

    // [No external calls.]

LICENSE

  Copyright 1998-2002 Forrest J. Cavalier III, http://www.mibsoftware.com
  Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block.
  License text in <librock/license/librock.txt> librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45

Source Code

./exec/algorithms/searching/ibsrch.c (implementation, plus source of this manual page)

Tests and Supported Platform Types

This is a representative sample. Librock code is highly portable. For a particular platform not reported here, request paid support

librock_ITERbinsearch passed tests in tibsearch_main (WIN32: 2002/08/08 sys=NT 4.0 using MSVC)
librock_ITERbinsearch passed tests in tibsrch (Unix/Linux/BSD: 2002/08/08 sys=FreeBSD using gcc)


This software is part of Librock

Rapid reuse, without rework. Details
This page copyright (C) 2002-2003 Forrest J. Cavalier III, d-b-a Mib Software, Saylorsburg PA 18353, USA

Verbatim copying and distribution of this generated page is permitted in any medium provided that no changes are made.
(The source of this manual page may be covered by a more permissive license which allows modifications.)

Want to help? We welcome comments, patches. -- Need help? Request paid support.