プログラマーが身につけなければならない10種類のアルゴリズム---二分検索アルゴリズム

3029 ワード

二分ルックアップアルゴリズムのコアコードは簡単ですが、配列がソートされている必要があります.
/*
*arr:      
*length:     
*value:     
*/
int search(int *arr,int length,int value)
{
    int head=0;
    int tail=length-1;
    int middle;

    //    (      )
    while(head<=tail)
    {
        middle=(head+tail)/2;
        if(arr[middle]>value)
            //      value ,  value    ,    head~middle-1  
            tail=middle-1;
        else
            if(arr[middle]1~tail  
                tail=middle+1;
            else
                return middle;
    }

    return -1;
}

int main()
{
    int arr[100];
    int length;
    int value;
    scanf("%d",&length);//      

    for(int i=0;i<length;i++)//      (     )
        scanf("%d",&arr[i]);

    scanf("%d",&value);

    int result = search(arr,length,value);

    if(result!=-1)
        printf("find it, position: %d",result);
    else
        printf("not exit.");

    getchar();
    return 0;
}