Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: After doing a lot of the problems on codingbat.com
Date: Fri, 27 Mar 2020 20:06:07 -0700
Organization: A noiseless patient Spider
Lines: 40
Message-ID: <86369t89gg.fsf@linuxsc.com>
References: <2f146b5c-e025-46ef-af7b-7c328c9f4206@googlegroups.com> <20200227200243.157a5e51fe7577f22aa37378@g{oogle}mail.com> <r396mg$uob$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="ba68f15be103986af77012e457fe73de"; logging-data="24887"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/7E9C+9Mxic6XfEsKNtV8Xz7WLiWQJJSM="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:h0QaQhNXR8fxf6tO39XoLAU+5Kw= sha1:HFhsGP6BcjRsJ6ZfLUCiUENhYG4=
Xref: csiph.com comp.lang.c:150868

Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:

[...]

> there's a lot more you can do with for() than just count loops
> [examples]
>
> - or even perform a binary search through an ordered array
> int *binsearch(int key, int array[], size_t nelement)
> {
>   size_t lowpt = 0,             /* lowest index in search range */
>          midpt,                 /* midpoint index;  where to search */
>          highpt = nelement - 1; /* highest index in search range */
>
>   /* LOOP through search UNTIL match found OR no elements left to search */
>   for (midpt = (lowpt+highpt)/2;                /* start in the middle */
>        array[midpt] != key && highpt > lowpt;   /* not found AND in bounds*/
>        midpt = (lowpt+highpt)/2)                /* compute new midpoint */
>   { /* ============================ **
>     ** array[midpt] was NOT a match **
>     ** ============================ */
>     if (key > array[midpt])
>       lowpt = midpt + 1;        /* narrow search to between here and high */
>     else
>       highpt = midpt - 1;       /* narrow search to beween low and here */
>   }
>
>   /* loop terminates when entry found OR no more array to search */
>
>   return (array[midpt] == key ? array+midpt : NULL);
> }

    int *
    search( int a[], unsigned n, int key ){
        return  n < 1            ?   0
            :   n == 1           ?   *a == key ? a : 0
            :   a[ n/2 ] > key   ?   search( a,     n/2,   key )
            :                        search( a+n/2, n-n/2, key );
    }