操屁眼的视频在线免费看,日本在线综合一区二区,久久在线观看免费视频,欧美日韩精品久久综

折半查找，也稱二分查找，在某些情況下相比于順序查找，使用折半查找算法的效率更高。但是該算法的使用的前提是靜態查找表中的數據必須是有序的。

也就是說，在使用折半查找算法查找數據之前，應該首先把該表的數據按照所查的關鍵字進行排序

折半查找算法

對靜態表查找表｛2，5，7，17，23，25，31，35，42，76，88｝采用折半查找算法查找關鍵字為17的關鍵字的過程為：

如上圖所示輸入關鍵詞進行查找，指針 low 和 high 分別指向查找表的第一個關鍵字和最后一個關鍵字，指針 mid 指向處于 low 和 high 指針中間位置的關鍵字。在查找的過程中每次都同 mid 指向的關鍵字進行比較，由于整個表中的數據是有序的，因此在比較之后就可以知道要查找的關鍵字的大致位置。

例如在查找關鍵字 17時，首先同 25作比較，由于17< 25，而且這個查找表是按照升序進行排序的，所以可以判定如果靜態查找表中有 17這個關鍵字，就一定存在于 low 和 mid 指向的區域中間。

因此，再次遍歷時需要更新 high 指針和 mid 指針的位置，令 high 指針移動到 mid 指針的左側一個位置上，同時令 mid 重新指向 low 指針和 high 指針的中間位置。如下圖所示

同樣，用 17同 mid 指針指向的 7作比較，7< 17，所以可以判定 17如果存在，肯定處于 mid 和 high 指向的區域中。所以令 low 指向 mid 右側一個位置上，同時更新 mid 的位置。

當第三次做判斷時輸入關鍵詞進行查找，發現 mid 就是關鍵字 17，查找結束

注意：在做查找的過程中，如果 low 指針和 high 指針的中間位置在計算時位于兩個關鍵字中間，即求得 mid 的位置不是整數，需要統一做取整操作。

折半查找的實現代碼：

#include 
#include 
#define keyType int
typedef struct {
    keyType key;//查找表中每個數據元素的值
    //如果需要，還可以添加其他屬性
}ElemType;
typedef struct{
    ElemType *elem;//存放查找表中數據元素的數組
    int length;//記錄查找表中數據的總數量
}SSTable;
//創建查找表
void Create(SSTable **st,int length){
    (*st)=(SSTable*)malloc(sizeof(SSTable));
    (*st)->length=length;
    (*st)->elem = (ElemType*)malloc((length+1)*sizeof(ElemType));
    printf("輸入表中的數據元素：\n");
    //根據查找表中數據元素的總長度，在存儲時，從數組下標為 1 的空間開始存儲數據
    for (int i=1; i<=length; i++) {
        scanf("%d",&((*st)->elem[i].key));
    }
}
//折半查找算法
int Search_Bin(SSTable *ST,keyType key){
    int low=1;//初始狀態 low 指針指向第一個關鍵字
    int high=ST->length;//high 指向最后一個關鍵字
    int mid;
    while (low<=high) {
        mid=(low+high)/2;//int 本身為整形，所以，mid 每次為取整的整數
        if (ST->elem[mid].key==key)//如果 mid 指向的同要查找的相等，返回 mid 所指向的位置
        {
            return mid;
        }else if(ST->elem[mid].key>key)//如果mid指向的關鍵字較大，則更新 high 指針的位置
        {
            high=mid-1;
        }
        //反之，則更新 low 指針的位置
        else{
            low=mid+1;
        }
    }
    return 0;
}
int main(int argc, const char * argv[]) {
    SSTable *st;
    Create(&st, 11);
    getchar();
    printf("請輸入查找數據的關鍵字：\n");
    int key;
    scanf("%d",&key);
    int location=Search_Bin(st, key);
    //如果返回值為 0，則證明查找表中未查到 key 值，
    if (location==0) {
        printf("查找表中無該元素");
    }else{
        printf("數據在查找表中的位置為：%d",location);
    }
    return 0;
}

運行結果為：