C++二分法在数组中查找关键字的方法

下面是“C++二分法在数组中查找关键字的方法”的完整攻略。

什么是二分法查找？

二分法查找（Binary Search），也称折半查找，是一种基于比较目标值与数组中间元素的常见查找算法。

如何在数组中使用二分法查找？

以下步骤描述如何在有序数组中使用二分法查找关键字：

定义左右边界：left = 0; right = 数组长度 - 1
循环 while (left <= right)
取数组的中间元素：mid = (left + right) / 2
如果中间元素等于要查找的关键字，返回 mid
如果中间元素小于要查找的关键字，此时关键字一定在 mid 的右侧，更新 left = mid + 1
如果中间元素大于要查找的关键字，此时关键字一定在 mid 的左侧，更新 right = mid - 1
若循环结束仍未找到关键字，返回 -1

二分法查找的时间复杂度和空间复杂度？

二分法查找的时间复杂度为 O(log n)，其中 n 为数组的长度。

空间复杂度为常量级别，即 O(1)。

二分法查找的关键代码实现示例

int binarySearch(int* arr, int len, int target) {
    int left = 0, right = len - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}

以上代码中，arr 表示有序数组，len 表示数组长度，target 表示要查找的关键字。

示例1：在有序数组中查找目标值

假设有一个有序数组 {1, 3, 5, 7, 9, 11}，现在要查找数字 7 在数组中的索引位置。

int arr[] = {1, 3, 5, 7, 9, 11};
int target = 7;
int len = sizeof(arr) / sizeof(int);
int index = binarySearch(arr, len, target);
if (index != -1) {
    printf("目标值在数组的第 %d 个位置\n", index + 1);
}
else {
    printf("数组中未找到目标值\n");
}

输出结果为：

目标值在数组的第 4 个位置

示例2：在有序数组中查找未出现的数字

假设有一个有序数组 {2, 4, 6, 8, 10}，现在要查找数字 5 在数组中的索引位置。

int arr[] = {2, 4, 6, 8, 10};
int target = 5;
int len = sizeof(arr) / sizeof(int);
int index = binarySearch(arr, len, target);
if (index != -1) {
    printf("目标值在数组的第 %d 个位置\n", index + 1);
}
else {
    printf("数组中未找到目标值\n");
}