请写一个二分查找 c++程序
时间: 2023-09-19 09:06:45 浏览: 51
### 回答1:
好的,以下是一个二分查找 C 语言程序:
```
#include <stdio.h>
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);
}
return -1;
}
int main(void)
{
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("元素不在数组中") : printf("元素在数组中的索引为 %d", result);
return 0;
}
```
该程序实现了一个二分查找的递归函数 `binarySearch`,以及一个测试该函数的主函数。
### 回答2:
二分查找是一种高效的查找方法,它可以在一个有序的数组中快速地找到指定的元素。下面是一个简单的二分查找的C语言程序:
```
#include <stdio.h>
// 二分查找函数
int binarySearch(int arr[], int target, int left, int right) {
while (left <= right) {
int middle = left + (right - left) / 2;
// 如果找到目标元素,返回它的下标
if (arr[middle] == target) {
return middle;
}
// 如果目标元素比中间元素小,说明它在左半边,更新右边界为 middle-1
if (arr[middle] > target) {
right = middle - 1;
}
// 如果目标元素比中间元素大,说明它在右半边,更新左边界为 middle+1
if (arr[middle] < target) {
left = middle + 1;
}
}
// 如果没有找到目标元素,返回 -1
return -1;
}
int main() {
int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) {
printf("目标元素不存在");
} else {
printf("目标元素在数组中的下标是:%d", result);
}
return 0;
}
```
在这个程序中,我们先定义了一个名为`binarySearch`的函数,该函数接受一个有序数组`arr`,目标元素`target`,以及数组的左右边界`left`和`right`作为参数。
函数内部使用一个`while`循环来不断缩小搜索范围,直到找到目标元素或者搜索范围为空。在每一次循环中,我们首先计算中间位置`middle`,然后与目标元素进行比较。
如果中间元素等于目标元素,我们就找到了目标元素,返回它的下标。
如果目标元素比中间元素小,说明它在左半边,我们更新搜索范围的右边界为`middle-1`。
如果目标元素比中间元素大,说明它在右半边,我们更新搜索范围的左边界为`middle+1`。
如果循环结束时仍然没有找到目标元素,我们就返回-1,表示目标元素不存在。
在`main`函数中,我们定义了一个有序数组`arr`,目标元素`target`,以及数组的长度`n`。
然后调用`binarySearch`函数来查找目标元素在数组中的下标。
最后根据返回值判断是否找到目标元素,并进行相应的输出。
### 回答3:
下面是一个用C语言实现的二分查找程序:
```c
#include <stdio.h>
// 二分查找函数
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // 若找到目标值则返回索引
}
if (arr[mid] < target) {
left = mid + 1; // 若当前中间值较小,说明目标值在右边,调整左边界
} else {
right = mid - 1; // 目标值在左边,调整右边界
}
}
return -1; // 若没有找到目标值则返回-1
}
// 示例函数
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1) {
printf("目标值 %d 不存在于数组中\n", target);
} else {
printf("目标值 %d 在数组中的位置是 %d\n", target, result);
}
return 0;
}
```
以上代码实现了一个用于在有序数组中进行二分查找的函数 `binarySearch`。在示例函数中,创建了一个有序数组 `arr`,然后调用 `binarySearch` 函数搜索目标值 `target` 在数组中的位置。最后根据返回值进行输出,若返回值为 -1 则表示目标值不存在于数组中,否则返回目标值在数组中的索引。