二分法是一種高效的查找方法，其適用于已經排好序的陣列
基本思路
從陣列最中間的數開始查找判斷，若不是需要查找的數字，則比較大小，之后則在從中間分開的兩邊中的一邊從最中間開始查找判斷，以此類推
演算法描述
這里以升序陣列為例，降序陣列類似
- 記錄陣列最中間數的下標，將其中的數與要查找的數進行比較
- 若相等，停止查找，若大于要查找的數，則將陣列下標上限換為較大半區的最小下標；若小于要查找的數，則將陣列下標的下限換為較小半區的最大下標
- 重復第一步，直到陣列下標不能調換，若查找到則停止查找，若未找到，則回傳不存在的結果
代碼實作
這里以升序陣列為例，降序陣列類似
# include<stdio.h>
int f(int, int [], int);
int main()
{
int n;
int arr[10]={1,2,3,4,5,6,7,8,9,10};
scanf("%d", &n);//輸入要查找的數
int m=f(n, arr, 10-1);
if(f(n, arr, 10-1)!=-1)
printf("該數所在下標為：%d\n", m);
else
printf("該數不存在\n");
}
int f(int n, int a[], int h)
{
int i, l, mid;
l = 0;
while(l<=h)//注意有等號,因為可能最后一次查找就只剩一個數,則這時上下限下標相等
{
mid=(l+h)/2;//計算中間下標
if(a[mid]==n)//判斷是否為目標數
return mid;
else if(a[mid]<n)
l=mid+1;//如果中間數小于目標數,則將陣列下限改為較大半區的下限
else
h=mid-1;//如果中間數大于目標數,則將陣列上限改為較小半區的上限
}
return -1;//回傳-1表示目標數不存在
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/59761.html
標籤：C
上一篇：選擇排序法（C語言）
下一篇：洗掉字串中的字符（C語言）