假如有一组无需关键字序列{39,11,68,46,75,23,71,8,86,34}请设计折半查找算法查找某一关键字key
时间: 2023-07-27 13:30:01 浏览: 46
好的,我可以给你设计一个基于折半查找算法的代码来查找某一关键字key。
折半查找又称二分查找,是一种非常高效的查找算法。它的基本思想是将有序序列分成两个部分,然后判断待查找的元素在哪一部分中,进而缩小查找范围,直到找到待查元素或者确定不存在。
下面是基于折半查找算法查找某一关键字key的代码实现:
```
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int key)
{
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main()
{
int arr[] = {39,11,68,46,75,23,71,8,86,34};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 75;
int result = binarySearch(arr, 0, n - 1, key);
if (result == -1)
printf("Element is not present in array\n");
else
printf("Element is present at index %d\n", result);
return 0;
}
```
对于给定的无序序列{39,11,68,46,75,23,71,8,86,34},我们可以将其排序后再使用折半查找算法进行查找,但是这样的时间复杂度为O(nlogn),不如直接使用线性查找算法。
因此,建议在使用折半查找算法时,先将序列进行排序,以提高算法效率。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)