C語言二分查找圖文詳解
一、二分查找算法
所謂二分查找,就是要在一組有序的數(shù)列中,查找給定的數(shù)是否在此數(shù)列中。
最主要的步驟有三個:
1.確定被查找的范圍的左右下標left、right
2.根據(jù)left和right,確定中間元素的下標mid
3.根據(jù)mid鎖定的元素和查找的元素比較,確定新的查找范圍left和right
下面將用圖示和代碼來講解上面的三個步驟:
1.假定給定的數(shù)組中元素個數(shù)為奇數(shù)個
2.假定給定的數(shù)組為偶數(shù)個
3.假定給定的數(shù)不在此數(shù)列中
根據(jù)以上這三種情況,代碼可以寫成如下形式:
#include <stdio.h> int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13 }; int left = 0, right = sizeof(arr) / sizeof(arr[0]) - 1; int x = 0,flag = 0; scanf("%d", &x);//要找的數(shù) while (left <= right)//若要找的數(shù)在此數(shù)組中,此條件會一直成立; //若要找的數(shù)不在此數(shù)組中,最終left會大于right,從循環(huán)中跳出 { int mid = (left + right) / 2; if (x == arr[mid]) { printf("%d\n", mid); flag = 1; break; } else if (x > arr[mid]) { left = mid + 1; } else { right = mid - 1; } } if (flag == 0)//只有當要找的數(shù)在數(shù)組中找不到時flag == 0 { printf("找不到\n"); } return 0; }
總結(jié):從上面的例子可以看出,二分法求解是一種很高效的方法,因為一次就可以排除一半的可能性。但也要注意,二分法只適用于有序數(shù)列
二、分支語句中應注意的小點
1.懸空else語句
#include <stdio.h> int main() { int a = 0; int b = 2; if (a == 1) if (b == 2) printf("hehe\n"); else printf("haha\n"); return 0; }
在上面的代碼中,有人可能就會對else語句與哪個if語句配對產(chǎn)生誤解。
其實:else是和它離的最近的if匹配的。但如果是像上面那樣寫就容易引起歧義??梢詫懗上旅娴男问剑?/p>
#include <stdio.h> int main() { int a = 0; int b = 2; if (a == 1) { if (b == 2) { printf("hehe\n"); } } else { printf("haha\n"); } return 0; }
適當?shù)氖褂脅}可以使代碼的邏輯更加清楚。
2.switch語句中的break
switch允許嵌套使用
#include <stdio.h> int main() { int n = 1; int m = 2; switch (n) { case 1: m++;//m == 3 case 2: n++;//n == 2 case 3: switch (n) {//switch允許嵌套使用 case 1: n++; case 2: m++;//m == 4 n++;//n == 3 break; } case 4: m++;//m == 5, n == 3 break; default: break; } printf("m = %d, n = %d\n", m, n); return 0; }
上面代碼中,有的case語句后沒有加上break,這就會導致執(zhí)行完一條沒有加break的case語句后還會執(zhí)行其下面的一條case語句,可能就會導致跟我們想要的判斷輸出結(jié)果不同。因為switch更多時候執(zhí)行的是條件判斷的功能,所以最好
在每一條有效的case語句后面都加上break。同時也要注意,在每個 switch 語句中都放一條default子句是個好習慣,甚至可以在后邊再加一個 break 。
總結(jié)
到此這篇關(guān)于C語言二分查找的文章就介紹到這了,更多相關(guān)C語言二分查找內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
c++ 獲取數(shù)字字符串的子串數(shù)值性能示例分析
這篇文章主要為大家介紹了c++ 獲取數(shù)字字符串的子串數(shù)值示例分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11