溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“C語言折半查找怎么實現”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
N 個有序整數數列已放在一維數組中，利用二分查找法查找整數 m 在數組中的位置。
若找到，則輸出其下標值；反之，則輸出 “ Not be found！”。
二分查找法（也叫折半查找）其本質是分治算法的一種。
所謂分治算法是指的分而治之，即將較大規模的問題分解成幾個較小規模的問題，這些子問題互相獨立且與原問題相同，通過對較小規模問題的求解達到對整個問題的求解。
我們把將問題分解成兩個較小問題求解的分治方法稱為二分法。需要注意的是，二分查找法只適用于有序序列。
二分查找的基本思想是：每次查找前先確定數組中待查的范圍，假設指針 low 和 high (low<high) 分別指示待查范圍的 下界 和 上界，指針 mid 指示區間的 中間位置，即 mid=(low+high)/2，把 m 與 中間位置 (mid) 中元素的值進行比較。
如果m的值大于中間位置元素中的值，則下一次的查找范圍放在中間位置之后的元素中；
反之，下一次的查找范圍放在中間位置之前的元素中。直到 low>high，查找結束。
N 個有序數應存放在數組中，根據數組下標的取值范圍知指針 low 和 high 的初值分別為 0、N-1。
除了三個指針變量 low、high、mid 之外還需要一個變量（假設為 k）來 記錄下標，利用變量 k 的值來 判斷整數是否在所給出的數組中。下面我們用示意圖來表示二分查找的過程。
假設一維數組中存儲的有序數列為：5 13 19 21 37 56 64 75 80 88 92，要查找的整數 m 為 21。
根據二分查找方法可知指針 low 和 high 最初分別指向元素 5 和 92，由 mid=(low+high)/2 知，指針 mid 指向元素 56。示意圖如下：
變量 m 所代表的整數 21 與 指針 mid 所指的元素 56 進行比較， 21 小于 56， 根據二分查找算法知， 查找范圍現在縮小到指針 mid 所指元素的前面， 即從 5~37 的范圍。
指針 high 原來指向下標為 N-1 的元素，現在指向下標為 mid-1 的元素，接著重新計算指針 mid 所指元素的下標。
再次進行比較，21 大于 19，現在比較范圍再次轉移到 mid 所指元素的后面，low 元素所指元素下標由 0 變為 mid+1。
當前 mid 所指元素的值為 21，與要查找的整數值相同，因此查找成功，所查元素在表中序號等于指針 mid 的值。
動圖解析
流程圖設計
完整代碼
#include <stdio.h>
#define N 10
int main()
{
int a[N] = { -3,4,7,9,13,45,67,89,100,180 };
int low = 0;
int high = N - 1;
int mid;
int i;
int m;
int k = -1;
printf("a 數組中的數據如下：");
for (i = 0; i < N; i++)
{
printf("%d ", a[i]);
}
printf("\n");
printf("Enter m：");
scanf("%d", &m);
while (low <= high)
{
mid = (low + high) / 2;
if (m < a[mid])
{
high = mid - 1;
}
else
{
if (m > a[mid])
{
low = mid + 1;
}
else
{
k = mid;
break;
}
}
}
if (k >= 0)
printf("m=%d index=%d\n", m, k);
else
printf("Not be found!\n");
}運行結果
代碼貼圖
程序分析
在上述程序中循環結束可以有兩種情況。
一種是由于循環的判定條件 low <= high 不成立的情況下跳出循環，此時可知查找不成功。
在查找不成功的情況下，語句 else {k=mid; break;} 是不執行的，所以變量 k 的值不變仍為初值 -1。
第二種結束循環的情況是由于執行了 break; 語句而跳出循環，在此情況下，變量 k 的值由 -1 變成了一個大于等于 0 的數，即指針 mid 所指元素的下標值。
所以在最后用選擇結構來判定 k 的值，從而確定整個查找過程是否成功。
continue 語句的格式為：
continue;
continue 語句用于循環語句（while循環語句 或 do...while循環語句 或 for循環語句）中，作為循環體的一部分。
在程序執行時，一旦遇到了 continue 語句，則立即結束本次循環，即跳過循環體中 continue 后面尚未執行的語句，接著進行是否繼續循環的條件判定。
break 語句的格式如下：
break;
break 語句 可用在 switch 語句中。
在程序執行時， 一旦遇到了 break 語句， 則立即退出當前的 switch 語句。
除此之外， break 語句還能用于循環語句（while循環語句 或 do...while 循環語句 或 for 循環語句)）中， 作為循環體的一部分。
在程序執行時， 一旦遇到了 break語句， 則立即退出當前的循環體，接著執行當前循環體下面的語句。
continue 只是結束本次循環，不再執行循環體中 continue 后面的其余語句，并不是終止當前循環。
break 是直接終止當前的循環。
在一個給定的數據結構中查找某個指定的元素，通常根據不同的數據結構，應采用不同的查找方法。對于一個有序數列，除了采用二分查找法之外還可以采用 順序查找 的方法。
順序查找一般是指 在線性表中查找指定的元素，其基本方法如下：
從線性表的第一個元素開始，依次將線性表的元素與被查元素進行比較，若相等則表示找到即查找成功；
若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素即查找失敗。
在長度為 n 的線性表中查找指定元素，最好的情況是比較一次成功，最壞的情況是比較 n 次，平均要比較(1＋2＋3＋⋅⋅⋅＋n)/n＝(1＋n)/2 次。
盡管順序查找的效率低，但對于一些情況只能采用順序查找的方法，如對于一個無序表進行查找。
完整代碼
#include <stdio.h>
#define N 10
int main()
{
int a[N] = { -3,4,7,9,13,45,67,89,100,180 }, i, m, k = -1;
printf("a數組中的數據如下: ");
for (i = 0; i < N; i++)
{
printf("%d ", a[i]); //輸出數組中原數據序列
}
printf("\n");
printf("Enter m: ");
scanf("%d", &m); //由鍵盤輸入要查找的整數值
for (i = 0; i < N; i++)
{
if (m == a[i])
{
k = i;
break; //一旦找到所要查找的元素便跳出循環
}
}
if (k >= 0)
printf("%m=%d index=%d\n", m, k);
else
printf("Not be found!\n");
return 0;
}運行結果
“C語言折半查找怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
