C语言程序题：写出递归与非递归两种折半查找程序，并分析其时间空间复杂度。

Question

写出递归与非递归两种折半查找程序，并分析其时间空间复杂度。
使用C语言编写

Answer 1

折半查找需要先对数据进行排序。

#include<iostream>
using namespace std;

int bSearch(int data[], const int x, int beg, int last)
{
int mid;
if (beg > last)
{
return -1;
}


while(beg <= last)
{
mid = (beg + last) / 2;
if (x == data[mid] )
{
return mid;
}
else if (data[mid] < x)
{
beg = mid + 1;
}
else if (data[mid] > x)
{
last = mid - 1;
}
}
return -1;
}



int  rBSearch(int data[], const int x, int beg, int last)
{

if(beg>last) return -1;
int mid = -1;
    mid = (beg + last) / 2;
if (x == data[mid])
{
return mid;
}
else if (x < data[mid])
{
return rBSearch(data, x, beg, mid - 1);
}
else if (x > data[mid])
{
return rBSearch(data, x, mid + 1, last);
}
}

int main(void)
{
int data[5] = {0};
//int num = 3;
int num=30;

cout << "The array is : " << endl;
int n = sizeof(data)/sizeof(int);
for (int i = 0; i < n; i++)
{
data[i] = i;
cout << data[i] << " ";
}
cout << endl;

int index = -1;
//index = bSearch(data,num,0,n);
index = rBSearch(data, num, 0,n);
cout << "Index of " << num << " is " << index << endl;
system("pause");
    return 0;
}

 以上是冒泡排序算法的实现。

折半查找算法描述如下：

在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：

1）     待查找数据值与中间元素值正好相等，则放回中间元素值的索引。

2）     待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），直到找到相等的值。

3）     待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），直到找到相等的值

4）     如果最后找不到相等的值，则返回错误提示信息。

 实现如下：

#include<iostream>
using namespace std;

int bSearch(int data[], const int x, int beg, int last)
{
int mid;
if (beg > last)
{
return -1;
}


while(beg <= last)
{
mid = (beg + last) / 2;
if (x == data[mid] )
{
return mid;
}
else if (data[mid] < x)
{
beg = mid + 1;
}
else if (data[mid] > x)
{
last = mid - 1;
}
}
return -1;
}



int  rBSearch(int data[], const int x, int beg, int last)
{
int mid = -1;
mid = (beg + last) / 2;
if (x == data[mid])
{
return mid;
}
else if (x < data[mid])
{
return rBSearch(data, x, beg, mid - 1);
}
else if (x > data[mid])
{
return rBSearch(data, x, mid + 1, last);
}
return -1;
}

int main(void)
{
int data[5] = {0};
int num = 3;

cout << "The array is : " << endl;
int n = sizeof(data)/sizeof(int);
for (int i = 0; i < n; i++)
{
data[i] = i;
cout << data[i] << " ";
}
cout << endl;

int index = -1;
//inedx=bSearch(data,num,0,n);
index = rBSearch(data, num, 0,n);
cout << "Index of " << num << " is " << index << endl;
system("pause");
    return 0;
}

复杂度分析：

折半查找就像搜素二叉树：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。折半查找法的查找次数正好为该值所在的层数。等概率情况下，约为log2(n+1)-1，其算法复杂度为O(log(n))。