二分法查找

版權聲明：本文為部落客原創文章，轉載請注明出處。 https://blog.csdn.net/twilight_karl/article/details/53257477

#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
#define max 20

typedef struct {
    int  data[max];
    int last;
}SequenList;


SequenList * init();                        //  建立順序表并初始化
int search(SequenList * ,int  );            //  二分法查找
void show(SequenList *);                    //展示元素

int main (){
    SequenList * head = init();
    show(head);
    int key ;
    int s ;
    while(1){
    fflush(stdin);
    scanf("%d",&s);
    key = search(head,s);
    if (key >= 0 ){
        printf("該元素的位置是: %d \n",key+1);
    }else{
        printf("\n找不到該元素\n");
    }
    }
    system("pause");
    return 0;
}

SequenList * init(){
    SequenList * p = (SequenList*)malloc(sizeof(SequenList));
    p ->last = 0;
    int i = 0;
    p->data[0] = rand()%10;
    for (i = 1 ; i < 10 ; i ++ ){
        p->data[i] = p->data[i-1]+ rand()%10;
        p->last++;
    }
    return p;
}

int search(SequenList *  p , int key ){
    int low ,middle,high ;
    low = 0;
    high = p->last;
    middle = (low+high)/2;
    while (low <= high){
        if (key > p->data[middle]){
            low = middle+1;
        }
        else if (key < p->data[middle]){
            high = middle-1;
        }else{
            return middle;
        }
        middle = (low+high)/2;
    }
    return -1;
}
void show(SequenList * p ){
    int i = 0 ;
    for (i = 0 ; i < p->last ; i ++){
        printf("%d ",p->data[i]);
    }
    printf("\n");
}           

運作結果如下