从一已经排序好的数据序列中,按折半查找方法查找一个数据x。 要求: (1) 采用递归算法实现; (2) 采用非递归算法实现。
时间: 2024-02-23 16:59:42 浏览: 23
好的,关于您的问题,我来回答一下。
首先来看递归算法实现折半查找:
```
int BinarySearch(int a[], int low, int high, int x)
{
if (low > high)
return -1;
int mid = (low + high) / 2;
if (a[mid] == x)
return mid;
else if (a[mid] > x)
return BinarySearch(a, low, mid - 1, x);
else
return BinarySearch(a, mid + 1, high, x);
}
```
其中,a[]是已经排序好的数据序列,low和high分别是序列的起始和结束下标,x是要查找的数据。递归的过程就是将待查找的区间不断缩小,直到找到x或者区间为空。
接下来是非递归算法实现折半查找:
```
int BinarySearch(int a[], int n, int x)
{
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] == x)
return mid;
else if (a[mid] > x)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
```
这个算法的实现和递归算法类似,只是将递归改成了循环,不断缩小待查找区间,直到找到x或者区间为空。
希望我的回答能够帮到您。