讲一遍C++中的二分查找

二分查找是一种常见的查找算法，也称为折半查找。它的前提是数据必须是有序的，每次查找都取中间位置的值与目标值进行比较，如果中间位置的值比目标值大，则在左半部分继续查找；如果中间位置的值比目标值小，则在右半部分继续查找，直到找到目标值或者查找区间为空为止。

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

int binarySearch(int nums[], int size, int target) {
    int left = 0;
    int right = size - 1; // 注意这里是 size - 1
    while (left <= right) {
        int middle = left + ((right - left) / 2);
        if (nums[middle] > target) {
            right = middle - 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    // 没找到就返回-1
    return -1;
}

在这个实现中，我们使用了一个while循环来不断缩小查找区间，直到找到目标值或者查找区间为空为止。每次循环中，我们都取中间位置的值与目标值进行比较，并根据比较结果来缩小查找区间。

相关问题

写一个c++的二分查找

好的，以下是一个简单的 C 语言二分查找代码示例：

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int x) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] < x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {2, 5, 7, 9, 14, 16};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 9;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        printf("Element not present");
    else
        printf("Element found at index %d", result);
    return 0;
}

在这个示例中，`binarySearch` 函数接收一个有序数组、左右索引和要查找的元素，返回该元素在数组中的索引，如果未找到则返回 -1。主函数定义了一个示例数组和要查找的元素，然后调用 `binarySearch` 函数并打印结果。

C++ STL 二分查找

以下是C++ STL中使用二分查找的示例代码：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> haystack {1, 3, 4, 5, 9};
    std::vector<int> needles {1, 2, 3};

    for (auto needle : needles) {
        std::cout << "Searching for " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle)) {
            std::cout << "Found " << needle << '\n';
        } else {
            std::cout << "no dice!\n";
        }
    }
}

这段代码使用了`std::binary_search`函数来进行二分查找。它接受一个有序范围（在本例中是`haystack`向量）和一个要查找的值（在本例中是`needle`）。如果找到了该值，则返回`true`，否则返回`false`。

在上述代码中，我们使用了一个循环来遍历`needles`向量中的每个元素，并对每个元素进行二分查找。如果找到了该元素，则输出"Found"，否则输出"no dice!"。