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; // 防止溢出的写法

        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, 15, 17, 19};
    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>
   using namespace std;

   引入了标准输入输出库和向量容器，并使用 std 命名空间以简化代码。

2. 二分查找函数：

   int binarySearch(const vector<int>& arr, int target)

   定义了一个名为 binarySearch 的函数，接受一个整数向量 arr 和一个目标值 target。该函数返回目标值在数组中的索引，如果找不到则返回 -1。

3. 初始化左右指针：

   int left = 0;
   int right = arr.size() - 1;

   初始化左右指针，分别指向数组的第一个和最后一个元素。

4. 循环查找：

   while (left <= right) {
       int mid = left + (right - left) / 2;

   使用 while 循环进行查找，直到 left 超过 right。计算中间位置 mid 时，采用 left + (right - left) / 2 的方式以防止溢出。

5. 比较中间值与目标值：

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

   根据中间值与目标值的比较结果调整左右指针的位置。

6. 返回结果：

   return -1;

   如果循环结束仍未找到目标值，则返回 -1。

7. 主函数：

   int main() {
       vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
       int target = 7;
   
       int result = binarySearch(arr, target);
   
       if (result != -1) {
           cout << "元素 " << target << " 在数组中的索引为: " << result << endl;
       } else {
           cout << "元素 " << target << " 不在数组中" << endl;
       }
   
       return 0;
   }

   在 main 函数中定义了一个有序数组 arr 和目标值 target，调用 binarySearch 函数并输出结果。