❶ 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語言二分法查找
#include <stdio.h>//不用math頭文件
void main()
{int high = 9,low = 0,m,k,a[10]={1,2,3,4,5,6,7,8,9,10};//hing和low賦初值
scanf("%d",&k);
while (high>=low)//>=
{
m=(high+low)/2;
if(k<a[m]) high=m-1;//比較的是數值而不是下標
else if(k>a[m]) low=m+1;
else
{
printf("yes");
return;//這兩句地方放錯了
}
}
printf("no");
return;//if語句去掉
}
❸ C語言中二分法的具體程序是什麼呢
舉個例子:
//二分查找法//
#
include
void
main()
{
int
a[16],i,num,flag=0,top,bottom,mid;
//定義一個一維數組a[16]用來存放供查找用的數據,但只用a[1]——a[15]//
//num用來放要查找的數據，flag是表示是否找到的開關變數，top表示查找的起始位置，bottom表示查找的終止位置，mid表示top與bottom的中間位置//
char
goon;
//變數goon為'y'或'Y'時表示繼續下一輪查找，否則終止程序//
printf("請輸入第1個數字：\n");
scanf("
%d",&a[1]);
//依次輸入第二到第十五個數，並要求輸入的數遞減//
for(i=2;i<=15;i++)
{
printf("請輸入第%d個數字：\n",i);
scanf("
%d",&a[i]);
if(a[i]>=a[i-1])
{
printf("請再次輸入，它應該比上一個數小：\n");
scanf("
%d",&a[i]);
}
}
//輸出剛才輸入的數//
printf("你剛才輸入的數是：\n");
for(i=1;i<=15;i++)
printf("
%d",a[i]);
printf("\n");
//查找循環開始//
do
{
printf("現在請輸入你要查找的數：\n");//輸入想要查找的數//
scanf("
%d",&num);
top=15;
bottom=1;
mid=15/2+1;
if(num>a[1]
||
num
0)//如果在規定的范圍內，開始二分法查找//
{
if(num==a[mid])//找到所需數據，退出本層循環//
{
printf("你所要查找的數字是第%d個。\n",mid);
flag=1;
}
else
if(num>a[mid])//如果要查找的數據比a[mid]大，在前半數組查找//
{
top=mid+1;
mid=(top+bottom)/2;
}
else
//如果要查找的數據比a[mid]小，在後半數組查找//
{
bottom=mid-1;
mid=(top+bottom)/2;
}
}
if(flag==0)//如果未找到數據，輸出找不到的信息//
printf("無法找到你要找的數字！\n");
printf("是否繼續查找？(Y/N)：\n");//詢問是否開始下一輪查找//
scanf("
%c",&goon);
}while(goon=='y'
||
goon=='Y');
}
❹ c語言如何實現-數組排序，二分查找
給定已經排好序的n個元素，現在要在這n個元素中找出一特定元素x。順序搜索的方法是逐個比較，直至找出元素。二分搜索則利用了元素間的次序關系，可大大提高效率。二分法的基本思想是將n個元素分成個數大致相同的兩半，取a[n/2]與x作比較。如果x==a[n/2]，則終止。如果x<a[n/2]，則只需在數組的左半部分繼續搜索。如果x>a[n/2]，則只需在右半部分搜索。本題要求利用上一題得到的數組進行順序查找和二分查找，分別為兩種查找方法計時。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void xuanzhe(int a[], int n)
{
int i, j, min, t;
for (i=0; i<n-1; i++) /*要選擇的次數：0~n-2共n-1次*/
{
min = i; /*假設當前下標為i的數最小，比較後再調整*/
for (j=i+1; j<n; j++)/*循環找出最小的數的下標是哪個*/
{
if (a[j] < a[min])
{
min = j; /*如果後面的數比前面的小，則記下它的下標*/
}
}
if (min != i) /*如果min在循環中改變了，就需要交換數據*/
{
t = a[i];
a[i] = a[min];
a[min] = t;
}
}
}
int main(){
int i,n,x;
int mid,left=0,right=999;
int find1=0,find2=0;
double y;
int a[1000];
for(i=0;i<1000;++i){
a[i]=rand();
}
xuanzhe(a,1000);
scanf("%d",&x);
printf("順序查找:\n");
for(i=0;i<1000;++i){
while(x==a[i]){
printf("找到X=%d,a[%d]\n",x,i);
find1=1;
break;
}
}
if(find1==0){
printf("沒有你要找的數\n");
}
printf("%fs\n",clock()/CLOCKS_PER_SEC);
y=clock();
printf("二分查找:\n");
while(!find2&&left<right)
{
mid=(left+right)/2;
if(x==a[mid])
find2=1;
else if(x<a[mid])
right=mid-1;
else left=mid+1;
}
if(find2==1)
printf("找到x=%d ,a[%d]\n",x,mid);
else
printf("沒有你要找的數\n");
printf("%fs\n",(clock()-y)/CLOCKS_PER_SEC);
}
❺ 誰能用c語言幫我寫個二分法的查找程序
#include<stdlib.h>
void
sort(int
a[],int
n){
/*排序函數，要使用二分法查找就必須對數組進行排序*/
int
i,k;
for(i=0;i<n;i++){
int
min=i;
for(k=i+1;k<n;k++)
if(a[min]>a[k])min=k;
if(i!=min){
a[min]+=a[i];/*這里是運用加減法交換兩個數*/
a[i]=a[min]-a[i];
a[min]-=a[i];
}
}
}
int
find(int
a[],int
n,int
key){/*二分法查找；參數：數組名，數組長度，查找關鍵字*/
int
min=0,max=n-1;/*二分法查找頭尾變數*/
while(min<max){/*如果最頭的變數值大於最尾變數的值，則查找不到，查找失敗*/
int
cen
=
(min+max)/2;
if(a[cen]==key)
return
cen;/*如果查到，則返回關鍵字在排序數組的下標*/
if(cen==min
||
cen==max)break;/*如果中間變數等於頭尾任一個變數，同樣查找失敗*/
if(a[cen]>key)
max=cen;
else
min=cen;
}
return
-1;
}
void
main(){/*主程序只是為了證明兩個函數的可行性，可以自己編寫*/
int
a[]={14,10,25,36,87,95,10,12,13,8},i;
sort(a,10);
i=find(a,10,11);
if(i!=-1)
printf("be
found");
else
printf("no
found");
getch();
}
❻ c語言中如何將順序表排序並實現二分法查找
voidInsertSort(sqR)
這個函數是按值傳遞參數的。換句話說，你的順序表在傳遞的時候被復制了一遍，然後這個函數收到的是一個副本，然後這個程序也許成功排序了這個副本，但是你原來的順序表並沒有改變。你可以考慮傳遞這個順序表的指針。比如這樣
voidInsertSort(sq*pR)
{
sqR=*pR;
//以下不變
...
}
調用的時候傳遞R的地址
InsertSort(&R);
❼ 如何用c語言的二分法查找從鍵盤輸入的任一個數是否在有序數列中
我運行過了，沒錯，基本符合你的要求，你可以試試看。
#include
<stdio.h>
#define
N
10
void
main()
{
int
i,number,top,bott,mid,loca,a[N],flag=1,sign;
char
c;
printf("請輸入10個數字:\n");
scanf("%d",&a[0]);
i=1;
while(i<N)
{scanf("%d",&a[i]);
if(a[i]>=a[i-1])
i++;
else
printf("輸入數字順序不是由小到大請重輸:\n");
}
printf("\n");
for(i=0;i<N;i++)
printf("%2d",a[i]);
printf("\n");
while(flag)
{printf("請輸入要查找的數字:");
scanf("%d",&number);
sign=0;
top=0;
bott=N-1;
if((number<a[0])||(number>a[N-1]))
loca=-1;
while((!sign)&&(top<=bott))
{mid=(bott+top)/2;
if(number==a[mid])
{loca=mid;
printf("在數組中發現數字
%d,在數組中該數字是第%d位\n",number,loca+1);
sign=1;
}
else
if(number<a[mid])
bott=mid-1;
else
top=mid+1;
}
if(!sign||loca==-1)
printf("在數組中沒有數字
%d.\n",number);
}
}