如何用C語言編寫半搜尋的演算法

#include

void main()

int in[15],ins,i,k=14,j=0;

printf("請按降序輸入 15 個數字");

for(i=0;i<15;i++)scanf("%d",&in[i]);

printf("請輸入您要查詢的號碼：");

scanf("%d",&ins);

i=(j+k)/2;

while(j<=k)

if(in[i]>ins)

k=i-1;

else if(in[i]j=i+1;

else break;

i=(j+k)/2;

printf("您正在尋找其中的 %d 個數字。 ",i+1);*i 是他儲存的序號，i+1 是他在輸入陣列中的位置數*

假設有 n 個數字被遵循上公升（這是關鍵！ 返回組）。把它放在一維陣列前面，怎麼找到你想要的數字？

顧名思義，二分法將一段數字分成兩半。

你想數進去它已經按公升序排列將案例與中位數進行比較時，有 4 種情況：

為什麼在發現數字 x 小於中間數字後設定 left=mid+1 和 right=mid-1？？它不能是 left=mid 和 right=mid？

這涉及到如果有兩個中位數（例如，圖中第乙個迴圈的中位數是 ），那麼系統將自動選擇它們左數字用作中間數 （21）。

那麼當需要檢索時是最後的數字，最後只剩下兩個邊界，所以不管怎麼錯過橙子的中間數，左右邊界的範圍都不會改變，左邊的邊界仍然是左邊的邊界。 而你需要檢索的數字是右邊的邊界，即使這個數字確實大於中間的數字，但是由於演算法的原因，中間的數字永遠不會是正確的邊界，所以永遠找不到右邊邊界上的數字。

但是，如果設定為 left=mid+1 和 right=mid-1，則可以使左邊框 = 右邊框，中間數等於該數字，以便進行比較並找到它。

至少 50 次關閉，60 次成功查詢。

首先，假設表格中的元素是按公升序排列的，將表格中間記錄的關鍵詞與搜尋關鍵詞進行比較，如果兩者相等，則搜尋成功。 否則，將表分成兩個子表，第乙個和最後乙個子表用於使用中間位置的正游泳記錄，如果中間位置記錄的關鍵字大於搜尋關鍵字，則進一步搜尋前乙個子表，否則進一步搜尋後乙個子表。

重複該過程，直到找到滿足條件的記錄，使查詢成功，或者直到子表不存在，此時查詢不成功。

基本思想是將 n 個元素分成兩半，數量大致相同（假設陣列元素按公升序排列），將 a[n 2] 與要查詢的 x 進行比較，如果 x=a[n 2]，則找到 x，演算法終止; 如果 xa[n 2]，那麼我們只需要繼續在陣列 a 的右半部分搜尋 x。

例如，排序後的資料為 1 5 12 35 64 78 89 123 456

如果要找 12，先用 12 將 （64） 與上面順序的 9 個數字中間的 12 < 64 進行比較，所以你要找的資料在前半部分，即 1 5 12 35 64，然後用 12 與前半部分的中間數字 （12） 進行比較， 所以你可以在 2 次搜尋後找到它。

半折搜尋的目的是為了提高搜尋效率！

折半搜尋方法是一種更有效的搜尋方法。

其基本思想是：設搜尋資料範圍的下限為l=0，上限為h=4，求中點m=（l+h）2，將x與中點元素am進行比較，如果x等於am，即找到並停止搜尋;

否則，如果 x 大於 am，則替換下限 l=m+1 並繼續在下半部分搜尋。 如果 x 小於 am，則將上限 h=m-1 更改為搜尋的上半部分。

重複上乙個過程，直到找到它或 l>h。 如果 l>h，則表示沒有這樣的數字，列印找不到資訊，程式結束。

步驟： 1.首先，確定整個搜尋間隔的中間位置mid=（left+right） 2 .

2、將要檢查的關鍵詞值與中間位置的關鍵詞值進行比較; 如果相等，則搜尋成功，如果大於該值，則在該區域的後（右）半部分繼續搜尋，如果小於則在區域的前（左）半部分繼續搜尋。

3.根據確定的減少面積減半的公式重複上述步驟。 結果是結束：要麼搜尋成功，要麼搜尋失敗。 半折搜尋的儲存結構儲存在一維陣列中。

二分查詢演算法也稱為半重查詢。 思路是將有序的序列依次儲存到陣列中，讓搜尋值為x，使用指標機械人指向序列的最左邊位置（最小值），將指標頂部指向序列的最右邊位置（最大值），取機械人和頂部的中間值指向序列的中間。

具體步驟說明如下： 當 top>bot 時，有三種可能性可以將 x 與 a[mid] 進行比較。

如果 x = a[mid]，則表示找到，退出比較查詢。

如果 x < a[mid]，則選擇前半部分繼續比較和搜尋，機械人保持不變，頂部變為 mid-1。

如果 x > a[mid]，選擇後半部分繼續比較和搜尋，機械人變為 mid+1，頂部保持不變。

有兩種方法可以結束該過程：一種是找到 x = a[mid]; 另乙個是找不到的，即排名靠前的<機械人。

二進位搜尋，也稱為二進位搜尋，是一種高效的搜尋方法。 但是，減半查詢要求線性表必須具有順序儲存結構，並且表中的元素按關鍵字按順序排列。

#includeusing namespace std;#define n 10 int half(int s,int a,int b,int key) }int main()

答案是補充的。 在查詢數字系列之前，您可能已經對它了解很多。 例如，您可以知道有序序列的一般分布。 如果知道有序序列中兩個相鄰元素之間差值的最大值的上限，則可以在將每個迴圈分成兩半之前過濾掉盡可能多的不需要的元素，這樣可以大大提高查詢速度。

在最壞的情況下，查詢元素的最大比較次數將在 1 和 [log2 n] 1 之間（n 是元素數）。 此外，在許多實際應用中，在建立有序序列的過程中可以同時獲得 m。 例如，在建立陣列的過程中，M可以根據新元素的插入而不斷更新，大大提高了每次查詢的效率。

你誤解了一半的查詢，你的最小值、最大值應該是下標而不是值。

原理：與求方程的二分法類似，二分搜尋首先比較序列中間的數字是否是要找到的數字，如果不是，因為是有序序列，然後看左邊或右邊的區間，丟棄不存在的一半區間， 然後在剩餘的時間間隔內重複該方法，直到找到數字，因為每次丟棄一半的資料量，因此搜尋效率更高。

說明：設左、右、中三個變數分別是序列兩側的下標和中間下標，當判斷不在左邊區間時，則左=中+1，這樣就可以用右半邊構造乙個新的區間，否則右=中間-1，用左邊構造乙個新區間， 然後重複剛才的過程，這樣如果你繼續往下走，要麼找到資料，要麼左>右，這個時候你也應該停止尋找，說明序列中沒有這個數字。

半折搜尋的基本思想是，對於乙個有序表，首先將表中間的 record 關鍵字與給定的關鍵字進行比較，如果相等，則搜尋成功; 如果給定的值大於 record 關鍵字，則在後半部分繼續減半搜尋; 否則，搜尋將在前半部分減半，直到搜尋範圍為空且找不到。

半分割搜尋的過程實際上確定了要找到的元素所在的區域，然後逐漸縮小區域，直到搜尋成功或失敗。

演算法中需要使用三個變數，low代表區域的下限，high代表上限，中間位置為mid=（low+high） 2

演算法：定義 maxlen n

int binsearch（datatype a,int k)

return -1;查詢失敗，返回 -1

這只是一種演算法，由你來使用它！

半折搜尋的基本思想是，對於乙個有序表，首先將表中間的 record 關鍵字與給定的關鍵字進行比較，如果相等，則搜尋成功; 如果給定的值大於 record 關鍵字，則在後半部分繼續減半搜尋; 否則，在假裝的前半部分，對折搜尋，直到搜尋範圍為空，找不到。

半分割搜尋的過程實際上確定了要找到的元素所在的區域，然後逐漸縮小區域，直到搜尋成功或失敗。

演算法中需要使用三個變數，low代表區域的下界，high代表上界，中間位置為mid=（low+high） 2

演算法：定義

maxlenn

intbinsearch（datatypea,intk)

intlow,high;

low=0;

high=maxlen-1;

while(low<=high)

mid=low+high)/2;

if(k==a[mid].key)

return

mid;如果搜尋成功，則返回被搜尋元素在表中的相對位置。

elseif(k>a[mid].key)

low=mid+1;

elsehigh=mid-1;

return

查詢失敗，返回 -1

這只是一種演算法，由你來使用它！