大连进口商品超市:高手进来看看，数据结构的一个问题
高手帮忙做一下
谢谢
1． 实现二分查找，函数原型为：int Binsch(int a[], int n, int k)。
其中a[]是数据数组，n是数组长度，k是被查找的数据，如果k再a[]中返回k的位置，否则返回-1。
要求：
1． 分析功能要求；
2． 分析算法复杂度。
照意思看应该是排过序的了
给个思路：
假设a[n]为升序
1、定义变量m1、m2、M，令m1=0，m2=n-1；
2、M = （m1+m2+1）/2，比较a[M]与k的大小：
如a[M]=k，返回M；
如a[M]>k,说明可能存在的k应该在a[M]项之前，所以让下一次搜索范围为前面的项目，即m2 = M-1，一旦m2<m1说明无结果返回-1；
如a[M]<k，同理m1 = M+1，一旦m1>m2说明无结果返回-1；
3、重复执行，直到有返回结果为止。
功能要求你自己写了，复杂度由于二分应该是log2(N)+1（最坏的情况），下面是简单代码：
#include "stdio.h"
int Find(int k,int a[],int n);
void main()
{
int n = 100;
int a[100];
for(int loop=0;loop<n;loop++)
{
a[loop] = loop*2; //只有偶数
}
int k,r;
scanf("%d",&k);
r = Find(k,a,n);
printf("Result is 第%d个\n",r);
}
int Find(int k,int a[],int n)
{
int M,m1,m2;
m1 = 0;
m2 = n-1;
do
{
M = (m1+m2+1)/2;
if(a[M]==k)
return M;
else if(a[M]>k)
{
m2 = M-1;
if(m2<m1)
return -1;
}
else if(a[M]<k)
{
m1 = M + 1;
if(m1>m2)
return -1;
}
}
while(1);
return 0;
}
数组a有没有排过序的啊？
没有的话二分查找没有意义的