[讨论][原创]折半查找可以这样吗?(页 1) - 数据结构与算法 - 编程论坛

SunShining 发表于 2006-3-16 21:21

[讨论][原创]折半查找可以这样吗?

这是我写的对半排序..请问可以吗? # include <stdio.h> int find(int k,int a[15],int x,int y) {int i,z,n=0; for(;x<=y;x++) n=n+1; z=y; for(i=1;i<=n/2;i++) z=z-1; if(i==1) {printf("There is nothing"); return;} if(k==a[z]) {printf("%d",z); return;} if(k>a[z]) {y=z; find(k,a[15],x,y);} if(k<a[z]) {x=z; find(k,a[15],x,y);} } main() {int a[15]; int i,k; for(i=0;i<15;i++) scanf("%d",&a[i]); scanf("%d",&k); find(k,a[15],0,14); getch(); } 是从大到小输入15个数...找个K的位置! 我用递归做的.不知道对不对?[em13]

星期八 发表于 2006-3-16 21:55

运行结果对就对嘛。。。

SunShining 发表于 2006-3-17 06:51

....不对..!

SunShining 发表于 2006-3-17 07:27

晕到..执行结果只是 There is nothing

无尘剑 发表于 2006-3-17 19:02

#include <stdio.h> #include<conio.h> int find(int k,int a[],int x,int y) { int i,z,n=0; for(;x<=y;x++) n=n+1; z=y; for(i=1;i<=n/2;i++) z=z-1; if(i==1) { printf("There is nothing"); return -1;} if(k==a[z]) { printf("%d",z); return -1;} else if(k>a[z]) {y=z; find(k,a,x,y);} //这里应用if-else结构 else if(k<a[z]) {x=z; find(k,a,x,y);} }
main() { int a[15]; int i,k; for(i=0;i<15;i++) scanf("%d",&a[i]); scanf("%d",&k); find(k,a,0,14); getch(); }

vfdff 发表于 2008-6-12 01:10

C++二分法查找

#include<iostream.h>//C++二分法查找
#define size 5
main()
{
//声明变量
int i,j;
float t,a[size];

//从键盘上为数组赋值
for (i=0;i<size;i++)
{
 cout<<"a["<<i<<"]=";
 cin>>a[i];
}

//使用冒泡排序法对数组按从小到大顺序排序
for (i=0;i<size-1;i++)
 for (j=i+1;j<size;j++)
 if (a[i]>a[j])
 {
 t=a[i];
 a[i]=a[j];
 a[j]=t;
 }

//显示排序结果
for (i=0;i<size;i++)
 cout<<a[i]<<" ";
cout<<endl;

//输入要查找的数据
int value;
int found; //找到为1，否则为0
int low,high,mid;
for (i=1;i<=3;i++) {
 cout<<"value=";
 cin>>value;

 //二分法（又叫折半查找法）查找数组a
 found=0;
 low=0;
 high=size-1;
 while(low<=high)
 {
 mid=(high+low)/2;
 if (a[mid]==value)
 {
 found=1;
 break;
 }
 if (a[mid]<value)
 low=mid+1;//mid往右移动
 else
 high=mid-1;//mid往左移动右逢源
 }
 if (found)//fond的初始值为0，一旦找到，found变量被置1,引发此条件语句，从而输出找到的结果，否则告知用户找不到。
 cout<<"The valu found at:a["<<mid<<"]="<<a[mid]<<endl;
 else
 cout<<"The "<<value<<" is not found!"<<endl;
}
}

vfdff 发表于 2008-6-12 01:11

在常规的二分查找法查找到一个符合条件数便会停止，如果数组中存在多个符合条件的数，并不会全部输出。
以下结合本人昨晚帮一位网友调试二分查找法练习程序时的一些思路，写了下面这个小程序，贴出来请大家审一下。
本人初学C++，有不当之处敬请指正，多谢。

//以下程序用VC++ 6.0编译并正常运行
// 二分查找法（折半查找法）实验及改进
// KKND 于 2004年9月7日晨

#include <iostream.h>
#include <stdlib.h> //由于使用了随机数 rand() 函数，所以需要包含这个头文件

#define ARR_MAX 100 //定义数组的最大长度

//为方便测试，此函数自动用随机数填充数组
void fillArray(int * Array,int Length,int Range);

//二分查找法要求查找目标是有序数组，此函数来对数组排序
void sortArray(int * Array,int Length);

//用二分法查找，改进后的搜索函数可查找出全部符合条件的数
//并输出找到数的数量和这些数在数中的位置
void searchNumber(int * Array,int Length,int Num);

void main()
{
int nArray[ARR_MAX];
int nLength=ARR_MAX; //指定在数组前 nLength 项进行操作
int nFillRange=50; //规定用来填充数组的随机数的取值范围
int nNum=0,nFind=0;
char cContinue;

fillArray(nArray,nLength,nFillRange); //填充数组
sortArray(nArray,nLength); //数组排序

loopSearchAgain:

cout<<endl<<"输入待查找的数:";
cin>>nNum; //取得待对比的整数

searchNumber(nArray,nLength,nNum); //查找

//询问是否继续在数组中查找新的数值
cout<<endl<<"按 'C' 键继续查找，其它键退出：";
cin>>cContinue;
if((cContinue='C')||(cContinue='c'))
{
 goto loopSearchAgain;
}
}

//填充
void fillArray(int * Array,int Length,int Range)
{
for(int i=0;i<Length;i++)
{
 Array[i]=rand() % Range;

 //cout<<"Array["<<i<<"]="<<Array[i]<<endl; //测试代码，用来输出填充过程
}
}

//排序
void sortArray(int * Array,int Length)
{
int i,j,t;
for(i=0;i<Length-1;i++)
{
 for(j=i;j<Length;j++)
 {
 if(Array[i]>Array[j])
 {
 t=Array[i];
 Array[i]=Array[j];
 Array[j]=t;
 }
 }
}
//for(i=0;i<Length;i++)cout<<"Array["<<i<<"]="<<Array[i]<<endl;//测试代码，用来输出排序结果
}

//查找
void searchNumber(int * Array,int Length,int Num)
{
int nStart=0,nEnd=Length-1,nMiddle,nFound=0;

while(nStart<=nEnd)
{
 nMiddle=(nStart+nEnd)/2;
 //cout<<"Start="<<nStart<<" End="<<nEnd<<" Middle="<<nMiddle<<endl;//测试代码，用来跟踪执行过程
 if(Array[nMiddle]==Num)
 {
 //如果找到，分别向两侧继续寻找条例条件的数
 //由于数组已经过排序，所以如果不止一个符合条件的数存在
 //那么这些数应一定是相邻的。
 nFound++;
 int nMin,nMax;

 nMin=nMiddle-1;
 nMax=nMiddle+1;
 //向上查找
 while(Array[nMin]==Num)
 {
 nFound++;
 nMin--;
 }
 //向下查找
 while(Array[nMax]==Num)
 {
 nFound++;
 nMax++;
 }
 //调整指示变量
 nMin++;
 nMax--;
 //输出查询结果
 if(nFound>1)
 {
 cout<<"找到 "<<nFound<<" 个符合条件的数，从 Array["<<nMin<<"] 到 Array["<<nMax<<"] 。"<<endl;
 break;
 }
 else
 {
 cout<<"在 Array["<<nMiddle<<"]找到一个符合条件的数。"<<endl;
 break;
 }
 }
 else if(Array[nMiddle]>Num) //判断方向，折半继续查找
 {
 nEnd=nMiddle-1;
 }
 else
 {
 nStart=nMiddle+1;
 }
}
if(nFound==0)cout<<"数组中没找到符合条件的数。"<<endl;
}

页: [1]

编程论坛's Archiver

[讨论][原创]折半查找可以这样吗?

C++二分法查找