c++二分查找算法

#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; // 防止溢出，等同于 (left + right) / 2

        if (arr[mid] == target) {
            return mid; // 找到目标值，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标值在右半部分
        } else {
            right = mid - 1; // 目标值在左半部分
        }
    }

    return -1; // 没有找到目标值，返回-1
}

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

    if (result != -1) {
        cout << "元素 " << target << " 在数组中的索引为: " << result << endl;
    } else {
        cout << "元素 " << target << " 不在数组中" << endl;
    }

    return 0;
}

解释说明：

1. 函数定义：binarySearch 函数接收一个整数数组 arr 和目标值 target，并返回目标值在数组中的索引。如果找不到目标值，则返回 -1。
2. 初始化左右指针：left 初始化为数组的第一个索引（0），right 初始化为数组的最后一个索引（arr.size() - 1）。
3. 循环条件：当 left 小于等于 right 时继续循环。
4. 计算中间位置：为了避免 (left + right) 可能导致的溢出问题，使用 left + (right - left) / 2 来计算中间位置。
5. 比较中间值与目标值：
   • 如果 arr[mid] == target，则找到了目标值，返回其索引。
   • 如果 arr[mid] < target，则目标值在右半部分，更新 left 为 mid + 1。
   • 如果 arr[mid] > target，则目标值在左半部分，更新 right 为 mid - 1。
6. 返回结果：如果循环结束仍未找到目标值，则返回 -1。
7. 主函数：main 函数中定义了一个有序数组 arr 和目标值 target，调用 binarySearch 函数并输出结果。

希望这段代码和解释对你理解二分查找算法有所帮助！