用c++写一个二分查找程序
时间: 2023-08-31 21:31:40 浏览: 102
回答1:
我可以为你编写一个二分查找程序,代码如下:int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2;
// 如果中间元素为要查找的元素,返回其索引
if (arr[mid] == x)
return mid;
// 如果要查找的元素小于中间元素,递归查找左子数组
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// 如果要查找的元素大于中间元素,递归查找右子数组
return binarySearch(arr, mid + 1, r, x);
}
// 如果查找元素不在数组中,返回 -1
return -1;
}
回答2:
二分查找(Binary Search)是一种在有序数组中查找特定元素的算法。它通过将待查找区间一分为二,然后确定目标值可能在的区间,再将该区间继续一分为二,直到找到目标值或者区间为空。
下面是用C语言编写的二分查找程序的示例:
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int target) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] > target)
return binarySearch(arr, left, mid - 1, target);
return binarySearch(arr, mid + 1, right, target);
}
return -1;
}
int main() {
int arr[] = {2, 5, 8, 12, 17, 21, 23};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 17;
int index = binarySearch(arr, 0, n - 1, target);
if (index == -1)
printf("目标值不在数组中");
else
printf("目标值在数组中的索引为:%d", index);
return 0;
}
在上面的程序中,binarySearch
函数是二分查找的实现。它接受一个有序整数数组arr
、数组的左边界left
、右边界right
和目标值target
作为参数。该函数使用递归的方式进行查找,不断将数组一分为二,直到找到目标值或者确定目标值不在数组中。
main
函数中,我们定义了一个有序数组arr
,并计算数组的长度。然后,我们指定了要查找的目标值为17。通过调用binarySearch
函数,在数组中查找目标值,若找到则返回目标值的索引,若未找到则返回-1。最后,根据返回的索引值,我们输出相应的结果。
以上就是用C语言编写的二分查找程序。希望对你有所帮助!
阅读全文