c语言二分法查找
时间: 2023-07-02 10:16:09 浏览: 63
二分法查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两部分,取中间值与目标值进行比较,如果中间值等于目标值,则查找成功;如果中间值大于目标值,则在左半部分继续查找;如果中间值小于目标值,则在右半部分继续查找。重复上述过程直到查找到目标值或者确定目标值不存在为止。
下面是一个用C语言实现的二分法查找的示例代码:
```c
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + ((right - left) >> 1); // 计算中间位置
if (arr[mid] == target) { // 如果中间位置的值等于目标值,返回该位置
return mid;
} else if (arr[mid] > target) { // 如果中间位置的值大于目标值,说明目标值在左半部分,缩小右边界
right = mid - 1;
} else { // 如果中间位置的值小于目标值,说明目标值在右半部分,缩小左边界
left = mid + 1;
}
}
return -1; // 如果没有找到目标值,返回-1
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1) {
printf("目标值不存在\n");
} else {
printf("目标值在数组中的位置是:%d\n", result);
}
return 0;
}
```
该示例代码中,我们定义了一个`binarySearch`函数,该函数接收四个参数:数组,左边界,右边界和目标值。函数通过while循环进行二分查找,如果找到目标值,返回该值在数组中的位置,否则返回-1。在主函数中,我们定义了一个有序数组,然后调用`binarySearch`函数进行查找,最后打印出结果。