C语言数据结构之 折半查找实例详解

什么是折半查找？

折半查找是一种在有序数组中查找某个特定元素的算法。其基本思想是将查找的值与数组的中间元素比较，如果比中间元素小，则在数组的左半部分查找；如果比中间元素大，则在数组的右半部分查找，直到找到该元素或查找范围为空。

折半查找算法的流程

1. 确定要查找的数组arr和其元素个数n，以及要查找的元素value。
2. 设定左边界low和右边界high初始值，即low=0，high=n-1。
3. 当low<=high时，执行以下步骤：
4. 计算中间位置mid = (low + high)/2，取整数部分；
5. 如果arr[mid] == value，则查找成功，返回mid；
6. 如果arr[mid] > value，则在左半部分继续查找，即将high = mid - 1；
7. 如果arr[mid] < value，则在右半部分继续查找，即将low = mid + 1；
8. 如果查找失败，返回-1。

折半查找的代码实现

int binary_search(int arr[], int n, int value)
{
    int low = 0;
    int high = n - 1;

    while (low <= high)
    {
        int mid = (low + high) / 2;

        if (arr[mid] == value)
        {
            return mid;
        }
        else if (arr[mid] > value)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }

    return -1;
}

折半查找的示例应用

示例1：在有序数组中查找指定元素

假设有一个有序数组arr，元素值为1、3、5、7、9、11、13、15、17、19，查找元素7，代码如下：

int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int n = sizeof(arr) / sizeof(int);
int value = 7;

int index = binary_search(arr, n, value);

if (index == -1)
{
    printf("查找失败\n");
}
else
{
    printf("查找成功，元素7的下标为%d\n", index);
}

运行结果为：

查找成功，元素7的下标为3

示例2：查找重复元素

折半查找也可用于查找重复元素，在查找到目标元素后可以向左和向右依次比较，查找其他相同的元素。代码如下：

int arr[] = {1, 3, 5, 7, 7, 7, 11, 13, 15, 17, 19};
int n = sizeof(arr) / sizeof(int);
int value = 7;

int index = binary_search(arr, n, value);

if (index == -1)
{
    printf("查找失败\n");
}
else
{
    printf("查找成功，元素7的下标为%d\n", index);
    int i = index - 1;
    while (i >= 0 && arr[i] == value)
    {
        printf("元素7的下标为%d\n", i);
        i--;
    }
    i = index + 1;
    while (i <= n - 1 && arr[i] == value)
    {
        printf("元素7的下标为%d\n", i);
        i++;
    }
}

运行结果为：

查找成功，元素7的下标为3
元素7的下标为2
元素7的下标为4