プログラミング珠玉第四章

本文にはプログラム設計方法学の内容が含まれている.詳しくは言わない
1、加算条件は0<=l   u<=n-1
2、この関数は次のように書くことができます.

int bs(int *a, int begin, int end, int v)
{
    int *b = a + begin, *e = a + end, *mid = NULL;
    if (!a) return NULL;

    while (b < e)
    {
        mid = b + ((e - b)>>1);
        if (*mid >= v) e = mid;
        else if(*mid < v) b = mid + 1;
    }
    if ((e-a) < end && (*e == v)) return e-a;
    return -1;
}

テストコードをもう1段与える

#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b)  
{  
    return (*(int*)a) - (*(int*)b);  
}

int bs(int *a, int begin, int end, int v)
{
    int *b = a + begin, *e = a + end, *mid = NULL;
    if (!a) return NULL;

    while (b < e)
    {
        mid = b + ((e - b)>>1);
        if (*mid >= v) e = mid;
        else if(*mid < v) b = mid + 1;
    }
    if ((e-a) < end && (*e == v)) return e-a;
    return -1;
}

int find(int *a, int begin, int end, int v)
{
    int i = 0;
    for (i = begin; i < end; ++i)
        if (a[i] == v) return i;
    return -1;
}

int main(void)
{
    int a[10000];
    int n = 10000, i = 0;
    int f, e;
    for (i = 0; i < n; ++i)
        a[i] = random()%100;
    qsort(a, n, sizeof(int), cmp);
    for (i = 0; i < n; ++i){
        f = find(a, 0, n, a[i]);
        e = bs(a, 0, n, a[i]);
        if (f != e)
            printf("Error find of %d %d %d
", a[i], f, e);
    }
    return 0;
}

3、4、5、省略
6、プログラムの終了性の証明に関して、つまり一歩ごとに少なくとも1つの豆が出てくるので、いつも終わります.無限ループはありません.また、白い豆は2つ持つか、投げないかのどちらかなので、白い豆は奇数であれば1つ残っています.
7、テーマの中で二分検索を採用するなら、探しているのは数のちょうど下界です.このブログでは、二分検索の補足方法を採用できます.