复试，机试必备二分法

包含迭代和递归两种实现方式：

迭代实现

#include <iostream>
#include <vector>

using namespace std;

// 二分查找的迭代实现
int binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 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;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;

    int result = binarySearch(arr, target);
    if (result != -1) {
        cout << "目标值 " << target << " 在数组中的索引是: " << result << endl;
    } else {
        cout << "目标值 " << target << " 不在数组中。" << endl;
    }

    return 0;
}

代码解释

1. 头文件包含：#include <iostream> 用于输入输出操作，#include <vector> 用于使用 vector 容器。
2. 命名空间使用：using namespace std; 让 std 命名空间里的标识符可直接使用。
3. binarySearch 函数： 接收一个有序的 vector<int> 类型数组 arr 和目标值 target。使用 left 和 right 表示查找范围的左右边界，初始时分别指向数组的开头和结尾。在 while 循环中，计算中间位置 mid，并比较 arr[mid] 与 target 的大小。如果相等则返回 mid；如果 arr[mid] 小于 target，则更新 left = mid + 1；如果 arr[mid] 大于 target，则更新 right = mid - 1。若循环结束仍未找到目标值，则返回 -1。
4. main 函数： 定义一个有序数组 arr 和目标值 target。调用 binarySearch 函数进行查找，并根据返回结果输出相应信息。

递归实现

#include <iostream>
#include <vector>

using namespace std;

// 二分查找的递归实现
int binarySearchRecursive(const vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;//等价int mid=(left+right)/2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;

    int result = binarySearchRecursive(arr, target, 0, arr.size() - 1);
    if (result != -1) {
        cout << "目标值 " << target << " 在数组中的索引是: " << result << endl;
    } else {
        cout << "目标值 " << target << " 不在数组中。" << endl;
    }

    return 0;
}

代码解释

1. binarySearchRecursive 函数： 除了接收数组 arr 和目标值 target 外，还接收左右边界 left 和 right。若 left > right，表示查找范围为空，返回 -1。计算中间位置 mid，并比较 arr[mid] 与 target 的大小。如果相等则返回 mid；如果 arr[mid] 小于 target，则递归调用 binarySearchRecursive 函数，更新左边界为 mid + 1；如果 arr[mid] 大于 target，则递归调用 binarySearchRecursive 函数，更新右边界为 mid - 1。
2. main 函数： 调用 binarySearchRecursive 函数进行查找，初始的左右边界分别为 0 和 arr.size() - 1。根据返回结果输出相应信息。