折半查找：

也稱二分查找，它是一種效率較高的查找方法，但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

創(chuàng)新互聯(lián)是一家專注于網(wǎng)站制作、成都網(wǎng)站建設(shè)與策劃設(shè)計(jì),斗門網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)10年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:斗門等地區(qū)。斗門做網(wǎng)站價(jià)格咨詢:13518219792

查找過(guò)程：
從表的中間記錄開(kāi)始，如果給定值和中間記錄的關(guān)鍵字相等，則查找成功；如果給定值大于或者小于中間記錄的關(guān)鍵字，則在表中大于或小于中間記錄的那一半中查找，這樣重復(fù)操作，直到查找成功，或者在某一步查找區(qū)間為空，則代表查找失敗。

折半查找每一次查找都使查找范圍縮小一半，與順序查找相比，很顯然會(huì)提高查找效率。

數(shù)據(jù)元素的定義：

typedef int KeyType ;

typedef struct {KeyType key;        //關(guān)鍵字域
}ElemType;

typedef struct {ElemType *R;        //存放查找表中元素的數(shù)組
    int length;         //記錄查找表中的長(zhǎng)度
}SSTable;

創(chuàng)建查找表：

void Create_List(SSTable *ss){int length;
    printf("請(qǐng)輸入元素個(gè)數(shù)：");
    scanf("%d",&length);
    ss->length = length;
    ss->R = (ElemType *)malloc((length + 1) * sizeof(ElemType)); //分配內(nèi)存
    printf("請(qǐng)依次輸入元素：");
    for(int i = 1;i<= length;i++){scanf("%d",&ss->R[i].key);
    }
}

排序：

由于上面寫的表并非是順序表，而且為了程序的開(kāi)放性，設(shè)定多一個(gè)排序，給表排序。這里利用冒泡排序。

冒泡排序：
是一種最簡(jiǎn)單的交換排序方法，它通過(guò)兩兩比較相鄰記錄的關(guān)鍵字，如果為逆序，則進(jìn)行交換，從而使關(guān)鍵字小的記錄如氣泡一般逐漸往上“漂浮”，或者使關(guān)鍵字大的記錄如石頭一般逐漸往下沉。

void Bubble(SSTable *ss,int length){printf("排序后的結(jié)果：");
    ss->R[0] = ss->R[1];//哨兵初始值
    for(int i=0;i//冒泡排序，循環(huán)遍歷
        for(int j=1;jif(ss->R[j].key >ss->R[j+1].key) {//交換數(shù)值
                int temp;
                temp=ss->R[j].key;
                ss->R[j].key=ss->R[j+1].key;
                ss->R[j+1].key=temp;
            }
        }
    }
    for(int i = 1;i<= ss->length;i++){printf("%d  ",ss->R[i].key);
    }
}

最后輸出排序結(jié)果，檢驗(yàn)。

折半查找

置查找區(qū)間初值，low為1，high為表長(zhǎng)。

當(dāng)low<=high 時(shí)，循環(huán)執(zhí)行：
mid取low和high的中間值；
將給定值x與中間位置記錄的關(guān)鍵字進(jìn)行比較，若相等則查找成功，返回中間位置mid；
若不相等，則利用中間位置記錄將表對(duì)分前、后兩個(gè)子表。

唯一注意的是，循環(huán)條件是 low<=high，而不是low

int Search(SSTable *ss,int x){int low = 1,high,mid;
    high = ss->length;
    while (low<= high){mid = (low + high) / 2;
        if (ss->R[mid].key == x){return mid;
        }
        else if (ss->R[mid].key< x){low = mid;
        }
        else if(ss->R[mid].key >x){high = mid;
        }
    }
}

完整代碼：

#include#includetypedef int KeyType ;

typedef struct {KeyType key;        //關(guān)鍵字域
}ElemType;

typedef struct {ElemType *R;        //存放查找表中元素的數(shù)組
    int length;         //記錄查找表中的長(zhǎng)度
}SSTable;

//創(chuàng)建查找表
void Create_List(SSTable *ss){int length;
    printf("請(qǐng)輸入元素個(gè)數(shù)：");
    scanf("%d",&length);
    ss->length = length;
    ss->R = (ElemType *)malloc((length + 1) * sizeof(ElemType)); //分配內(nèi)存
    printf("請(qǐng)依次輸入元素：");
    for(int i = 1;i<= length;i++){scanf("%d",&ss->R[i].key);
    }
}

//排序
void Bubble(SSTable *ss,int length){printf("排序后的結(jié)果：");
    ss->R[0] = ss->R[1];//哨兵初始值
    for(int i=0;i//冒泡排序，循環(huán)遍歷
        for(int j=1;jif(ss->R[j].key >ss->R[j+1].key) {//交換數(shù)值
                int temp;
                temp=ss->R[j].key;
                ss->R[j].key=ss->R[j+1].key;
                ss->R[j+1].key=temp;
            }
        }
    }
    for(int i = 1;i<= ss->length;i++){printf("%d  ",ss->R[i].key);
    }
}

//二分查找法
int Search(SSTable *ss,int x){int low = 1,high,mid;
    high = ss->length;
    while (low<= high){mid = (low + high) / 2;
        if (ss->R[mid].key == x){return mid;
        }
        else if (ss->R[mid].key< x){low = mid;
        }
        else if(ss->R[mid].key >x){high = mid;
        }
    }
}

int main() {SSTable ss;
    int x,location;
    Create_List(&ss);
    Bubble(&ss,ss.length);
    while (1){printf("\n請(qǐng)輸入需要查找的元素：");
        scanf("%d",&x);
        Search(&ss,x);
        location = Search(&ss,x);
        if (location == 0){printf("查找失??！\n");
        } else{printf("數(shù)據(jù)在查找表中的位置為：%d\n",location);
        }
    }
    return 0;
}

在主函數(shù)也給一個(gè)while的死循環(huán)，方便多次查找，不用查找一次運(yùn)行一次代碼。

這個(gè)代碼出現(xiàn)一個(gè)bug，就是會(huì)在查找時(shí)候出現(xiàn)卡住，出不了結(jié)果的情況

希望有大佬幫幫忙看看什么情況 嘻嘻~
如果有錯(cuò)，望指出更正。向大家學(xué)習(xí)！

最后：這是我一次數(shù)據(jù)結(jié)構(gòu)作業(yè)。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)折半查找（二分查找）-創(chuàng)新互聯(lián)
分享路徑：http://jinyejixie.com/article4/jjooe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、全網(wǎng)營(yíng)銷推廣、面包屑導(dǎo)航、虛擬主機(jī)、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)