3.1 算法简介

<aside> 🪬

二分查找算法（Binary Search Algorithm）：也叫做折半查找算法、对数查找算法，是一种用于在有序数组中查找特定元素的高效搜索算法。

</aside>

二分查找的基本算法思想为：通过确定目标元素所在的区间范围，反复将查找范围减半，直到找到元素或找不到该元素为止。

3.2 二分查找的步骤：

  1. 初始化边界：设定两个指针 low 和 high，分别指向数组的开头和结尾。
  2. 中间值比较：取中间值 mid = (low + high) // 2，比较目标值 target 和 arr[mid]：
  3. 重复步骤2，直到找到目标值或者 low > high（表示查找失败，目标值不存在）。

示例：

在有序数组 [1, 2, 4, 6, 9, 13, 16] 中查找目标值 9：

  1. low = 0, high = 6，mid = 3，arr[3] = 6，因为 6 < 9，更新 low = 4。
  2. low = 4, high = 6，mid = 5，arr[5] = 13，因为 13 > 9，更新 high = 4。
  3. low = 4, high = 4，mid = 4，arr[4] = 9，找到目标值，返回索引 4。

Python实现：

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2  # 计算中间位置
        if arr[mid] == target:
            return mid  # 找到目标，返回索引
        elif arr[mid] < target:
            low = mid + 1  # 目标在右半部分
        else:
            high = mid - 1  # 目标在左半部分
    return -1  # 目标不存在

# 测试
arr = [1, 2, 4, 6, 9, 13, 16]
target = 9
result = binary_search(arr, target)
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found")

C++实现：

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 防止溢出
        if (arr[mid] == target) {
            return mid;  // 找到目标，返回索引
        } else if (arr[mid] < target) {
            low = mid + 1;  // 目标在右半部分
        } else {
            high = mid - 1;  // 目标在左半部分
        }
    }
    return -1;  // 目标不存在
}

int main() {
    int arr[] = {1, 2, 4, 6, 9, 13, 16};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int result = binarySearch(arr, n, target);
    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }
    return 0;
}

关键点总结：