用C++编写一个实现二分查找的算法

以下是 C++ 实现二分查找的代码示例：

int binary_search(vector<int> arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

该函数接受一个有序数组 `arr` 和目标元素 `target`，返回目标元素在数组中的下标，如果不存在则返回 -1。

算法的核心部分是循环内的判断，如果当前中间元素等于目标元素，则直接返回下标；如果中间元素小于目标元素，则在右半部分继续查找；否则在左半部分查找。由于每次查找都将目标区间缩小一半，因此时间复杂度为 O(log n)。

注意：该函数的参数 `vector<int> arr` 表示使用了 C++ 中的标准库 `vector` 来存储数组。如果使用原始数组，则需要传递数组的指针和长度作为参数。

相关问题

用c++编写算法实现二分检索

二分查找（Binary Search），也称折半查找，是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

C++实现代码如下：

#include <iostream>
using namespace std;

// 二分查找算法
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;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 没有找到目标元素，返回-1
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    int index = binarySearch(arr, 0, n - 1, target);
    if (index != -1) {
        cout << "目标元素 " << target << " 在数组中的下标是 " << index << endl;
    } else {
        cout << "目标元素 " << target << " 不在数组中" << endl;
    }
    return 0;
}

上述代码中，`binarySearch` 函数使用迭代的方式实现了二分查找算法，其中参数 `arr` 表示要进行查找的数组，`left` 表示数组的左边界，`right` 表示数组的右边界，`target` 表示要查找的目标元素。

在函数体中，首先使用 while 循环不断地比较数组中间位置的元素和目标元素的大小关系，然后根据比较结果将搜索范围缩小到数组的左半部分或右半部分，直到最终定位到目标元素或者搜索范围为空时退出循环。如果找到目标元素，就返回其在数组中的下标；否则返回 -1 表示目标元素不在数组中。

在主函数中，我们定义了一个数组 `arr`，然后调用 `binarySearch` 函数查找数组中是否包含目标元素，最后根据查找结果输出相应的提示信息。

用c++写一个二分查找程序

### 回答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语言编写的二分查找程序。希望对你有所帮助！