查找算法之二分查找的C++实现

什么是二分查找？

二分查找（Binary Search），也叫折半查找，是一种在有序数组中查找某一特定元素的查找算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种查找算法每次比较都使搜索范围缩小一半，其时间复杂度为$O(\log n)$。

二分查找的实现过程

下面是二分查找的实现过程：

1. 首先把数组按照大小排列，确保其是有序的。

2. 然后选择数组的中间元素，与要查找的数进行比较。

3. 如果相等，则查找成功，返回该元素所在的位置。

4. 如果中间元素大于查找的元素，则在数组的左半部分继续进行二分查找。

5. 如果中间元素小于查找的元素，则在数组的右半部分继续进行二分查找。

6. 如果查找到最后都没有找到，则查找失败，返回-1。

二分查找的C++代码实现

int binarySearch(int arr[], int start, int end, int target) {
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

上述代码中，我们使用了循环结构实现二分查找。函数的参数包括：要查找的数组、数组起始位置、数组结束位置以及待查找的元素。

二分查找的示例

下面通过两个示例，介绍二分查找的使用方法。

示例一：查找元素

假设有一个有序数组为{1, 2, 3, 4, 5, 6, 7, 8, 9}，现在要查找元素5，代码如下：

#include <iostream>

using namespace std;

int binarySearch(int arr[], int start, int end, int target) {
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int len = sizeof(arr) / sizeof(int);
    int index = binarySearch(arr, 0, len - 1, 5);
    if (index >= 0) {
        cout << "查找成功，元素5所在位置为：" << index << endl;
    } else {
        cout << "查找失败，未找到元素5" << endl;
    }
    return 0;
}

运行上面的代码，输出结果如下：

查找成功，元素5所在位置为：4

示例二：查找符合条件的元素

假设有一个有序数组为{1, 2, 3, 3, 4, 4, 4, 5, 6, 7, 8, 9}，现在要查找第一个值大于等于4的元素所在的位置，代码如下：

#include <iostream>

using namespace std;

int binarySearch(int arr[], int start, int end, int target) {
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] >= target) {
            if (mid == 0 || arr[mid - 1] < target) {
                return mid;
            } else {
                end = mid - 1;
            }
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 3, 4, 4, 4, 5, 6, 7, 8, 9};
    int len = sizeof(arr) / sizeof(int);
    int index = binarySearch(arr, 0, len - 1, 4);
    if (index >= 0) {
        cout << "查找成功，第一个值大于等于4的元素所在位置为：" << index << endl;
    } else {
        cout << "查找失败，未找到符合条件的元素" << endl;
    }
    return 0;
}

运行上面的代码，输出结果如下：

查找成功，第一个值大于等于4的元素所在位置为：4