二分检索法c语言
时间: 2023-07-09 18:23:48 浏览: 44
二分查找也称折半查找,是一种在有序数组中查找特定元素的搜索算法。在二分查找每次将待查找的区间缩小一半,直到找到目标元素或者区间为空为止。
下面是一个简单的二分查找示例程序:
```c
#include<stdio.h>
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
l = mid + 1;
else
r = mid - 1;
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
```
其中 `binarySearch` 函数接收一个有序数组 `arr`,左右边界 `l` 和 `r`,和目标元素 `x`,返回目标元素在数组中的下标(如果找到)或者 -1(如果未找到)。
函数采用迭代的方式实现,每次都将待查找的区间缩小一半。如果中间元素等于目标元素,返回下标;如果中间元素小于目标元素,说明目标元素在右侧,将左边界调整为中间位置加一;如果中间元素大于目标元素,说明目标元素在左侧,将右边界调整为中间位置减一。如果最终未找到目标元素,返回 -1。
在本例中,程序输出 "Element is present at index 3",因为目标元素 10 在数组中的下标为 3。