数据结构二分查找算法c语言
时间: 2023-11-03 16:06:52 浏览: 47
引用中提到的二分查找算法是一种通过比较中间元素与目标元素来缩小查找范围的算法。它所以被称为“二分”,是因为每次查找都将查找范围分为两部分,然后再确定目标元素位于哪一部分,从而减少了查找的次数。
在二分查找算法中,首先需要确定查找范围的起始位置和结束位置,然后计算中间位置。通过比较中间位置的元素与目标元素的大小关系,可以进一步确定目标元素位于左半部分还是右半部分,从而缩小查找范围。如果中间元素等于目标元素,则查找成功;如果中间元素大于目标元素,则在左半部分继续查找;如果中间元素小于目标元素,则在右半部分继续查找。重复以上步骤,直到查找到目标元素或者确定目标元素不存在。
以下是一个使用C语言实现的二分查找算法的示例代码:
```c
#include <stdio.h>
int binary_search(int arr[], int n, int target) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main() {
int arr[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
int n, addr;
printf("请输入待查找的关键字: ");
scanf("%d", &n);
addr = binary_search(arr, 11, n);
if (addr != -1) {
printf("查找成功,关键字 %d 所在的位置是: %d\n", n, addr);
} else {
printf("查找失败!\n");
}
return 0;
}
```
以上代码中,`binary_search`函数接受一个已排序的数组、数组的大小和目标元素作为参数,并返回目标元素在数组中的位置(如果存在),否则返回-1。在`main`函数中,我们定义了一个已排序的数组`arr`,然后输入待查找的关键字,并调用`binary_search`函数进行查找,最后输出查找结果。