用c++写个二分查找算法
时间: 2023-05-25 07:01:43 浏览: 77
A:
```c
int binary_search(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
这个算法接收三个参数:一个已排序的整数数组 `arr`,数组的元素数量 `n` 以及要查找的目标值 `target`,并返回目标值在数组中的下标,如果目标值不存在则返回 -1。
该算法使用了迭代方式进行二分查找。它初始化左右边界为数组的首尾元素下标,然后进入循环。在每次迭代中,它计算出当前左右边界的中间位置 `mid`,如果 `arr[mid]` 等于 `target`,则直接返回 `mid`。如果 `arr[mid]` 小于 `target`,则将左边界移动到 `mid + 1`。反之,如果 `arr[mid]` 大于 `target`,则将右边界移动到 `mid - 1`。直到左右边界相遇并且没有找到目标值时,算法退出并返回 -1。
相关问题
用c++写一个二分查找算法
当然可以,以下是一个简单的二分查找算法的 C 代码:
```
int binary_search(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
其中,`arr` 是一个已经排好序的数组,`n` 是数组的长度,`target` 是要查找的目标值。函数返回目标值在数组中的下标,如果目标值不存在,则返回 -1。
希望这个代码能够帮到你!
用C++写二分查找递归算法
当在一个有序数组中查找一个元素时,二分查找算法是一种高效的搜索方法。以下是使用C语言编写的递归算法示例:
```c
#include <stdio.h>
int binary_search_recursive(int arr[], int low, int high, int target) {
if (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binary_search_recursive(arr, mid + 1, high, target);
} else {
return binary_search_recursive(arr, low, mid - 1, target);
}
}
return -1;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int index = binary_search_recursive(arr, 0, n - 1, target);
if (index == -1) {
printf("Element not found in array");
} else {
printf("Element found at index %d", index);
}
return 0;
}
```
该递归算法将数组分为两半,并检查目标元素是否在左半部分、右半部分或中间位置。如果目标元素在左半部分,递归地调用函数并在左半部分进行二分查找;如果目标元素在右半部分,同样递归地调用函数并在右半部分进行二分查找;如果目标元素与中间元素匹配,函数将返回中间元素的索引。如果目标元素不在数组中,函数将返回-1。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)