Ⅰ C語言遞歸函數如何實現二分搜索演算法
折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，已知一個有n個元素的有序序列, 將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x, 直到找到x或者是沒有找到!
如果是常規的方法的話那麼我們可以通過循環的方式, 按照上面說的演算法, 找到則退出循環, 否則繼續循環直到左下標位置小於或者等於右下標的位置.
按兄弟你的意思是要用遞歸方法進行搜索, 那麼大概還是上面的演算法, 只是把循環的方式改成遞歸方式: 如果沒找到,則確定新的搜索范圍, 即左右下標新位置, 然後把新的參數傳給函數繼續調用函數進行遞歸搜索!!
遞歸方式實現詳細代碼如下:
#include <stdio.h>
#define ARRAY_SIZE 10
#define NOT_FOUND -1
int BinarySearch(int array[], int left, int right, int NumToSearch)
{
int mid = (left + right) / 2;
if (left <= right)
{
if (NumToSearch == array[mid])
{
return mid;
}
else if (NumToSearch < array[mid])
{
right = mid - 1;
return BinarySearch(array, left, right, NumToSearch);
}
else
{
left = mid + 1;
return BinarySearch(array, left, right, NumToSearch);
}
}
return NOT_FOUND;
}
int main()
{
int a[ARRAY_SIZE] = {2, 5, 6, 7, 13, 20, 22, 27, 112, 222};//假設一個已知的有序且是升序數列
int result = 0;//查找的結果
int x = 13;//假設我們要查找的數是13
int left = 0;//序列開始下標
int right = ARRAY_SIZE - 1;//序列結尾下標
result = BinarySearch(a, left, right, x);
if (result == NOT_FOUND)
{
printf("Not Found!\n");
}
else
{
printf("Found %d in array a, it is a[%d]\n", x, result);
}
return 0;
}
希望對兄弟你有幫助!
Ⅱ 用C語言編寫非遞歸演算法實現折半查找（二分查找）
char
a[10][5];//按字典序遞增
int
search(char
*x)//二分查找，返回有序表中大於等於x的元素位置
{
int
low=0,high=9,mid,t;
while(low<=high)
{
mid=(low+high)/2;
t=strcmp(a[mid],x);//比較中點位置與x
if(t==0)
return
mid;//相等返回其位置
else
if(t>0)
high=mid-1;//x小於mid元素，則在中點前
else
low=mid+1;
}
return
high+1;//返回大於x的第一個元素
}
這個是我曾經用過的字元串的二分查找~
請根據需要修改數據類型。。。
Ⅲ 順序表的排序，二分法查找的c語言程序
#include<stdio.h>
int fun(int a[],int n,int key)
{i
nt low,mid,high;//low、mid、high是三個索引分別指向數組的下標low=0;//low指向數組a[]的第一個元素，即下表為0的元素
high=n-1;//lhigh指向數組a[]的最一個元素，即下表為n-1的元素，n為數組的長度
while(low<=high)//循環終止條件是low>high的時候
{
mid=(low+high)/2;//所謂二分查找就在這里，每次都讓mid指向數組下標等於low和high之和的一半的元素i
f(key<a[mid])//如果a【mid】大於要查找的元素，說明要查找的元素在low和mid之間，這是需要把high重新置為mid-1
(high=mid-1);//這里應該是{}，不能使（）吧
else if(key>a[mid])//這里同理，如果a【mid】小於要查找的元素，說明要查找的元素在mid和high之間，這是需要把low重新置為mid+1
(low=mid+1);
else
return mid;//剩下的就是相等的情況，直接返回mid就是查找到的結果
}
return -1;//執行到這一步就說明，low>high，沒有找到要查找的元素，返回-1表示沒有結果
}
main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int a,b,c;
b=4;
c=fun(a,10,b);
if(c==1)
printf("not found");
else
printf("psition %d\n",c);
}