【程式設計珠玑】第四章 編寫正确的程式

1、對下标限定界限：加條件 0<=l u<=n-1

2、這個函數可以寫成如下形式：

#include <iostream>
using namespace std;

int bs(int *a, int begin, int end, int v)  
{  
    int *b = a + begin; //開始 
    int *e = a + end;   //結束 
    int *mid = NULL;    //中間 


    while (b < e)  //直到等于第一個出現的值 
    {  
        mid = b + ((e - b)>>1);  //得到中間位置的位址 

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

    return -1;  
}  
int main()
{
    int a[5]={1,2,2,2,4};
    cout<<bs(a, 0, 4, 2)<<endl;
    return 0;
}      

再給一段測試代碼

#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\n", a[i], f, e);  
    }  
    return 0;  
}      

6、程式終止性證明：即每一步都至少會扔出一個豆子，是以總會結束的。此外，白色的豆子要麼拿兩個，要麼不扔，是以白色的豆子如果是奇數，則會留下一個白豆子，否則是黑豆子。

7、題目裡面如果要采用二分搜尋，那麼需要找的是一個數的剛好下界。

采用題目2中的方法，可以找到剛好上界，由于，線段是順序排列的，是以就可以找剛好的下界了。