C语言经典算法之折半查找算法

发布时间:2024年01月17日

目录

前言

A.建议

B.简介

一 代码实现

二 时空复杂度

A.时间复杂度:

B.空间复杂度:

三 优缺点

A.优点:

B.缺点:

四 现实中的应用


前言

A.建议

1.学习算法最重要的是理解算法的每一步,而不是记住算法。

2.建议读者学习算法的时候,自己手动一步一步地运行算法。

tips:文中的对数均以2为底数

B.简介

折半查找算法,也称为二分查找算法,是一种在有序数组中查找特定元素的高效算法。这种查找算法的基本思想是通过将查找范围逐渐缩小一半,最终找到目标元素或确定目标元素不存在。

 

一 代码实现

#include <stdio.h>

// 二分查找函数
int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;

        // 如果目标值在中间
        if (arr[mid] == target) {
            return mid;
        }

        // 如果目标值在左半部分
        if (arr[mid] > target) {
            high = mid - 1;
        }
        // 如果目标值在右半部分
        else {
            low = mid + 1;
        }
    }

    // 如果数组中不存在目标元素
    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 12;

    int result = binarySearch(arr, 0, n - 1, target);

    if (result != -1) {
        printf("元素 %d 在数组中的索引是 %d。\n", target, result);
    } else {
        printf("元素 %d 不在数组中。\n", target);
    }

    return 0;
}

在这个示例中,binarySearch 函数接受一个有序数组 arr,查找范围的起始索引 low 和结束索引 high,以及要查找的目标元素 target。函数使用一个循环来逐步缩小查找范围,直到找到目标元素或确定其不存在。最后,程序输出目标元素在数组中的索引或提示元素不存在。

tips:为了确保二分查找的正确性,数组必须是有序的。

二 时空复杂度

A.时间复杂度:

折半查找每次将查找范围缩小一半,因此其时间复杂度是对数级别的。在每一步中,查找范围都被缩小为原来的一半,所以即使在大规模数据集中,也能迅速地找到目标元素。其时间复杂度为O(log n)


B.空间复杂度:

折半查找算法的空间复杂度是常数级别的,因为它仅需要使用常数级别的额外空间来存储一些变量,如索引、中间位置等。空间复杂度不随输入规模的增加而增加。其空间复杂度为O(1)

三 优缺点

A.优点:

高效性: 折半查找的时间复杂度为O(log n),在大规模数据集中仍然能够快速找到目标元素。相较于线性查找等较低效的查找算法,折半查找通常更为迅速。

适用性: 折半查找主要适用于有序数组。如果数组有序,可以充分利用这一特性,在每一步中将查找范围缩小一半,提高查找效率。

简单性: 实现折半查找的算法相对简单,代码不复杂。只需通过比较目标值与中间元素的大小关系,就能够迅速决定搜索范围。

B.缺点:

要求有序: 折半查找要求数组事先有序。如果数组无序,需要先进行排序,这会增加额外的时间开销。在频繁变动的数据集中,维持有序状态可能会带来一些不便。

不适用于链表: 折半查找通常用于数组,不太适用于链表等非连续存储结构。链表无法像数组一样通过索引直接访问元素,因此折半查找的实现相对复杂。

插入和删除操作相对复杂: 当需要在有序数组中插入或删除元素时,可能需要移动一部分元素,使得这两个操作的时间复杂度相对较高。相较之下,二叉搜索树可能更适合频繁进行插入和删除操作。

四 现实中的应用

数据库检索: 数据库中的索引结构通常采用有序数组或者有序链表,折半查找可以用来快速检索数据库中的记录。数据库索引的设计常常利用折半查找来提高查询性能。

字典查找: 在字典、词典等有序文本数据结构中,折半查找可以用来快速查找单词或者条目。这在自然语言处理、文本编辑软件等应用中经常会用到。

查找特定值: 在一些应用中,需要从一个有序的数据集中查找某个特定值,例如查找股票价格、图书价格等。折半查找可以有效地缩小搜索范围,提高查找效率。

文件系统搜索: 在文件系统中,文件名通常按字母顺序排列。折半查找可以用来在文件系统中快速定位文件,尤其是在大型文件系统中。

游戏中的排名和积分: 在在线游戏中,玩家的排名和积分通常按照某种顺序排列。折半查找可以用来迅速查找某个玩家的排名或者积分。

网络路由表: 在网络路由表中,IP地址通常是有序的。路由表的查询操作可以使用折半查找来快速找到目标IP地址对应的路由信息。

学生成绩查询: 在学生成绩单中,学生的成绩按照学号或姓名的顺序排列。折半查找可以用于快速查询某个学生的成绩。

文章来源:https://blog.csdn.net/weixin_56154577/article/details/135649145
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。