C++二分查找(折半查找)算法实例详解

C++二分查找(折半查找)算法实例详解

什么是二分查找(折半查找)算法？

二分查找(折半查找)算法是一种在有序数组中查找某一特定元素的搜索算法。查找流程是先将数组元素按照大小排序，然后每次将待查找元素与数组的中间元素进行比较，不断缩小查找范围，直到找到目标元素，或者确定目标元素不存在于数组中。

二分查找(折半查找)算法示例

算法流程

1.首先确定数组的左右边界left和right，其中left=0，right=n-1，n为数组元素个数。

2.计算中间元素mid，其中mid=(left+right)/2。

3.比较待查找元素与中间元素大小，如果相等，则查找成功并返回对应的数组下标；如果待查找元素小于中间元素，则在串左半部分继续查找；否则，在串右半部分继续查找。

4.通过不断重复以上步骤，直到找到目标元素或者确定目标元素不存在于数组中。

示例1

假设有一个有序数组A={1,2,3,4,5,6,7,8,9}，要在其中查找元素5的位置，以下是C++代码实现：

#include <iostream>
using namespace std;

int BinarySearch(int A[], int n, int x)
{
    int left = 0;  // 左边界
    int right = n - 1;  // 右边界
    while (left <= right)
    {
        int mid = (left + right) / 2;  // 中间元素
        if (A[mid] == x)  // 找到目标元素
            return mid;
        else if (A[mid] > x)  // 目标元素在左半部分
            right = mid - 1;
        else  // 目标元素在右半部分
            left = mid + 1;
    }
    return -1;  // 目标元素不存在
}

int main()
{
    int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(A) / sizeof(A[0]);
    int x = 5;  // 目标元素
    int result = BinarySearch(A, n, x);
    if (result == -1)
        cout << "元素不存在" << endl;
    else
        cout << "元素下标为：" << result << endl;
    return 0;
}

输出结果为：

元素下标为：4

示例2

假设有一个有序数组A={1,2,3,4,5,6,7,8,9}，要在其中查找元素10的位置，以下是C++代码实现：

#include <iostream>
using namespace std;

int BinarySearch(int A[], int n, int x)
{
    int left = 0;  // 左边界
    int right = n - 1;  // 右边界
    while (left <= right)
    {
        int mid = (left + right) / 2;  // 中间元素
        if (A[mid] == x)  // 找到目标元素
            return mid;
        else if (A[mid] > x)  // 目标元素在左半部分
            right = mid - 1;
        else  // 目标元素在右半部分
            left = mid + 1;
    }
    return -1;  // 目标元素不存在
}

int main()
{
    int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(A) / sizeof(A[0]);
    int x = 10;  // 目标元素
    int result = BinarySearch(A, n, x);
    if (result == -1)
        cout << "元素不存在" << endl;
    else
        cout << "元素下标为：" << result << endl;
    return 0;
}

输出结果为：

元素不存在

从以上两个示例可以看出，二分查找(折半查找)算法适用于有序数组，时间复杂度为O(log n)，效率非常高，可以快速地查找数组中的元素。