当前位置：首页 > article >正文

每天学习一个基础算法之二分查找

article 2024/11/19 19:33:02

目录

前言：

1、对二分查找概念的诠释

2、二分查找的使用场景

3、对比顺序查找与二分查找时间复杂度

4、二分查找的实现代码

代码主体（以接口函数的形式）

实现思路：

测试部分（主函数调用）

调试结果

前言：

前一篇博客我们已经介绍学习了顺序查找法，它在对有序数据查找时效率较低，而当我们要对有序数据进行查找时就要用到二分查找法了，所以今天我们要学习的就是二分查找法。

1、对二分查找概念的诠释

二分查找也称折半查找，二分查找从数据结构的中间位置开始，如果中间位置的数据正好与给定数据相同，则查找成功；否则利用中间位置将数据分成前后两个部分，如果中间元素大于给定的数据，则继续在前一半数据中查找，否则继续在后一半数据中查找，重复此操作，直到找到与给定数据相同的数据或全部数据找完。

2、二分查找的使用场景

二分查找比顺序查找的效率高，但它必须要求待查找的数据的结构是有序排列的，适用于不经常变动且查找频率较高的有序数据。

3、对比顺序查找与二分查找时间复杂度

顺序查找上篇博客已经说了其本质上就是对数组进行遍历，所以顺序查找的时间复杂度为O(N)，而二分查找的时间复杂度为O(log2n)，这意味着在最坏的情况下，算法的执行时间与以2为底的目标值的对数成正比，这使得二分查找在处理大规模数据时非常高效。

4、二分查找的实现代码

代码主体（以接口函数的形式）

//二分查找法的实现
static int binary_seek(int arr[], int sz, int target)
{
    int left = 0;
    int right = sz - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] > target)
        {
            right = mid - 1;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

实现思路：

和前一篇博客顺序查找相同，我采取的方式仍为若找到与给定值相同的数据，返回其下标，若最终找完所有数据还没找到则返回-1。

在程序中，我用left代表排查数据段首元素地址；用right代表排查数据段末尾元素地址;用mid代替排查数据段中间元素地址。

根据概念的理解

如果中间位置的数据正好与给定数据相同对应：

return mid;

如果中间元素大于给定的数据，则继续在前一半数据中查找对应：

right = mid - 1;

否则继续在后一半数据中查找对应：

left = mid + 1;

测试部分（主函数调用）

int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    
    int ret = binary_seek(arr, sz, 7);
    if (ret != -1)
    {
        printf("下标为%d\n", ret);
    }
    else
    {
        printf("没找到！\n");
    }
    return 0;
}