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