c语言用折半查找法在(05 13 19 21 37 56 64 75 80 88 92)表中査找元素21。
时间: 2023-06-11 21:07:52 浏览: 298
利用数组进行数据查找--折半查找法介绍-c语言编程——计算机专业的教材
折半查找法,也称二分查找,是一种高效的查找算法,在有序数组中查找一个元素的时间复杂度为 O(log n)。
具体步骤如下:
1. 定义变量:left = 0,right = n-1,mid = (left + right) / 2。
2. 判断中间元素是否等于要查找的元素,如果是则返回其下标;如果不是,则继续执行下一步。
3. 如果中间元素大于要查找的元素,则在左半部分继续查找,即令 right = mid - 1;否则在右半部分查找,即令 left = mid + 1。
4. 重复步骤2和步骤3,直到找到要查找的元素或者 left > right。
按照上述步骤进行折半查找,可以得到元素21的下标为3。
具体代码如下:
```
#include <stdio.h>
int binary_search(int arr[], int n, int target) {
int left = 0, right = n-1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
int main() {
int arr[] = {5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 21;
int index = binary_search(arr, n, target);
if (index == -1)
printf("未找到元素%d", target);
else
printf("元素%d的下标为%d", target, index);
return 0;
}
```
阅读全文