二分算法（二分查找）

2024-03-18 20:19:50

发布于：北京

19阅读

0回复

0点赞

汇总
二分算法（Binary Search Algorithm）是一种用于在有序数组中查找特定元素的高效算法。它通过将目标值与数组中间元素进行比较，从而逐步缩小搜索范围，直到找到目标值或确定其不存在为止。以下是关于二分算法的详细说明和示例代码：

二分算法详解

算法原理

首先，对于有序数组，确定搜索范围的左右边界；
计算中间元素的索引，比较中间元素与目标值；
如果中间元素等于目标值，则返回结果；
如果中间元素大于目标值，则在左半部分继续搜索；
如果中间元素小于目标值，则在右半部分继续搜索；
重复以上步骤，直到找到目标值或确定其不存在。

示例：（C++）

#include <iostream>
#include <vector>

int binarySearch(std::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() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;

    int result = binarySearch(arr, target);

    if (result != -1) {
        std::cout << "Element found at index: " << result << std::endl;
    } else {
        std::cout << "Element not found in the array." << std::endl;
    }

    return 0;
}