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

目录

前言

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.时间复杂度：

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

B.空间复杂度：

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

三 优缺点

A.优点：

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

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

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

B.缺点：

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

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

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

四 现实中的应用

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

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

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

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

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

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

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