C/C++ 常用的四种查找算法

简介: 在计算机科学中,搜索算法是一种用于在数据集合中查找特定元素的算法。C语言作为一种强大的编程语言,提供了多种搜索算法的实现方式。本文将介绍C语言中的四种常见搜索算法其中包括(线性查找,二分法查找,树结构查找,分块查找),并提供每种算法的简单实现示例。

在计算机科学中,搜索算法是一种用于在数据集合中查找特定元素的算法。C语言作为一种强大的编程语言,提供了多种搜索算法的实现方式。本文将介绍C语言中的四种常见搜索算法其中包括(线性查找,二分法查找,树结构查找,分块查找),并提供每种算法的简单实现示例。

常见的查找算法主要有以下几种:

  1. 线性查找(Linear Search):
    • 简单直观,适用于无序列表。
    • 从列表的一端开始逐个元素比较,直到找到目标元素或遍历完整个列表。
  2. 二分查找(Binary Search):
    • 适用于有序列表。
    • 每次将目标值与中间元素比较,可以迅速缩小搜索范围。
  3. 树结构查找(树的各种形式,如二叉搜索树、AVL树、红黑树等):
    • 通过树结构,可以更加高效地进行查找、插入和删除操作。
    • 二叉搜索树要求左子树上所有结点的值小于根结点的值,右子树上所有结点的值大于根结点的值。
  4. 分块查找(Block Search):
    • 将数据分成若干块,每一块中的元素无序,但块与块之间有序。
    • 先确定目标元素所在的块,再在块内进行线性查找。

这些查找算法各自有适用的场景和优势,选择合适的查找算法取决于数据的特性以及实际应用的需求。

线性查找(Linear Search)

线性搜索,又称为顺序搜索(Sequential Search),是一种简单直观的查找算法。该算法通过顺序遍历数据集,逐一比较每个元素与目标值是否相等,直到找到目标值或遍历完整个数据集。

算法步骤

  1. 从头到尾遍历数据集: 从数据集的第一个元素开始,依次比较每个元素与目标值是否相等。
  2. 比较目标值: 对于每个元素,与目标值进行比较。
  3. 找到目标值: 如果找到了与目标值相等的元素,返回该元素的位置或索引。
  4. 遍历完整个数据集: 如果遍历完整个数据集仍未找到目标值,返回未找到的标记(通常是一个特殊值,如-1)。

特点

  1. 适用于小型数据集: 线性搜索适用于小型数据集,对于大型数据集可能效率较低。
  2. 无序数据: 不依赖数据的排列顺序,适用于无序数据。
  3. 简单直观: 实现简单,易于理解。

线性搜索是最简单的搜索算法之一,它按顺序遍历数据集合,查找目标元素。以下是一个线性搜索的C语言示例:

#include <stdio.h>

int linearSearch(int arr[], int n, int target)
{
   
    for (int i = 0; i < n; i++)
    {
   
        if (arr[i] == target)
        {
   
            return i; // 找到则返回索引
        }
    }
    return -1; // 未找到则返回-1
}

int main(int argc, char *argv[])
{
   
    int arr[] = {
   1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    int result = linearSearch(arr, n, target);
    if (result != -1)
    {
   
        printf("元素在索引 %d 处找到\n", result);
    } else
    {
   
        printf("未找到元素\n");
    }
    return 0;
}

二分查找(Binary Search)

二分搜索(Binary Search)是一种在有序数组中查找目标值的算法。它通过反复将查找范围划分为两半并比较目标值与中间元素的大小,从而缩小搜索范围,直到找到目标值或确定目标值不存在。

算法步骤

  1. 初始化: 确定搜索范围的起始点 left 和终止点 right
  2. 循环条件:left 小于等于 right 时执行循环。
  3. 计算中间位置: 计算中间位置 midmid = (left + right) / 2
  4. 比较目标值: 将目标值与中间元素进行比较。
    • 如果目标值等于中间元素,找到目标,返回索引。
    • 如果目标值小于中间元素,说明目标值在左半部分,更新 right = mid - 1
    • 如果目标值大于中间元素,说明目标值在右半部分,更新 left = mid + 1
  5. 循环结束:left 大于 right,表示搜索范围为空,未找到目标值。

特点

  1. 有序数组: 二分搜索要求数组是有序的,以便通过比较中间元素确定目标值在哪一半。
  2. 高效性: 由于每一步都将搜索范围缩小一半,因此二分搜索的平均时间复杂度为 O(log n)。
  3. 适用性: 适用于静态数据集或很少变化的数据集,不适用于频繁插入、删除操作的动态数据集。

二分搜索要求数据集合是有序的,以下是一个二分搜索的C语言示例:

#include <stdio.h>

int binary_search(int key, int a[], int n)
{
   
  int low, high, mid, count = 0, count1 = 0;
  low = 0;
  high = n - 1;
  while (low<high)
  {
   
    count++;                    // 记录查找次数
    mid = (low + high) / 2;     // 求出中间位置
    if (key<a[mid])             // 当key小于中间值
      high = mid - 1;         // 确定左子表范围
    else if (key>a[mid])        // 当key大于中间值
      low = mid + 1;          // 确定右子表范围
    else if (key == a[mid])     // 当key等于中间值证明查找成功
    {
   
      printf("查找元素: %d Array[%d]=%d\n", count, mid, key);
      count1++;            //count1记录查找成功次数
      break;
    }
  }
  if (count1 == 0)
    return 0;
}

int main(int argc, char *argv[])
{
   
  int number = 10, key = 6;
  int Array[10] = {
    1, 5, 6, 7, 9, 3, 4, 6, 0, 2 };

  binary_search(key, Array, number);

  return 0;
}

二叉搜索树 (BST)

二叉搜索树(Binary Search Tree,BST)是一种二叉树数据结构,其中每个节点都有一个键值,且满足以下性质:

  1. 对于树中的每个节点,其左子树中的所有节点的键值都小于该节点的键值。
  2. 对于树中的每个节点,其右子树中的所有节点的键值都大于该节点的键值。
  3. 左、右子树也分别为二叉搜索树。

这个性质使得在二叉搜索树中可以高效地进行搜索、插入和删除操作。

特点

  1. 有序性: 由于BST的定义,其中的元素是有序排列的。对于任意节点,其左子树的值小于该节点,右子树的值大于该节点,因此通过中序遍历BST可以得到有序的元素序列。
  2. 高效的搜索操作: 由于有序性,可以通过比较键值快速定位目标节点,使搜索操作的平均时间复杂度为 O(log n)。在最坏情况下(树退化为链表),搜索的时间复杂度为 O(n)。
  3. 高效的插入和删除操作: 插入和删除操作也涉及到比较键值和调整树的结构,平均情况下的时间复杂度为 O(log n)。在最坏情况下,树可能变得不平衡,导致时间复杂度为 O(n),但通过平衡二叉搜索树(如 AVL 树、红黑树等)可以保持树的平衡。

操作

  1. 搜索(Search): 从根节点开始比较目标值,根据比较结果选择左子树或右子树,直到找到目标节点或达到叶子节点。
  2. 插入(Insert): 从根节点开始,按照比较结果选择左子树或右子树,直到找到合适的插入位置,插入新节点。
  3. 删除(Delete): 找到要删除的节点,可能有以下几种情况:
    • 若该节点为叶子节点,直接删除。
    • 若该节点有一个子节点,用子节点替代该节点。
    • 若该节点有两个子节点,找到右子树中的最小节点或左子树中的最大节点,替代该节点,并递归删除被替代的节点。

以下是一个简化的BST的C语言示例:

#include <stdio.h>
#include <stdlib.h>

struct Node
{
   
    int key;
    struct Node *left, *right;
};

struct Node* newNode(int key)
{
   
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = node->right = NULL;
    return node;
}

struct Node* insert(struct Node* root, int key)
{
   
    if (root == NULL)
        return newNode(key);
    if (key < root->key)
        root->left = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
    return root;
}

int main(int argc, char *argv[])
{
   
    struct Node* root = NULL;
    int keys[] = {
   3, 1, 5, 2, 4};
    for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++)
    {
   
        root = insert(root, keys[i]);
    }
    // 可以在 'root' 上执行BST操作
    return 0;
}

分块查找(Block Search)

分块搜索(Block Search)是一种在查找大量数据中的目标值时,将数据分成若干块,然后在块内进行查找的策略。这种方法适用于一些动态更新频繁,但每次更新数据量较小的场景。

算法步骤

  1. 数据分块: 将大量数据按照一定的规则分成若干块。
  2. 建立索引表: 对每个块建立索引,记录每块的起始位置、结束位置和关键字(通常是块内最大的关键字)。
  3. 查找块: 根据目标值的大小确定它可能在哪个块中,找到相应的块。
  4. 在块内查找: 在确定的块内使用线性查找或其他查找算法寻找目标值。

特点

  1. 适用于动态数据: 分块搜索适用于数据集动态更新的情况,因为每次更新数据只需更新相应块的索引。
  2. 索引表: 建立索引表有助于快速定位目标值可能存在的块,提高查找效率。
  3. 非均匀分块: 可以根据数据的特点进行非均匀分块,以适应不同数据分布情况。

该查找与二分查找类似,都是对半分,分块则可以分为多块,效率更高一些。如下这段C语言代码实现了分块查找算法。分块查找是一种基于块的数据结构的搜索算法,通过将数据集划分为若干块(或称为块),并为每个块建立一个索引。每个索引记录了该块的起始位置、结束位置以及该块内元素的最大值。

#include <stdio.h>

struct index           //定义块的结构
{
   
  int key;
  int start;
  int end;
}index_table[4];       //定义结构体数组

int block_search(int key, int a[])          //自定义实现分块查找
{
   
  int i, j;
  i = 1;
  while (i <= 3 && key>index_table[i].key)      //确定在哪个块中
    i++;
  if (i>3)                                  //大于分得的块数,则返回0
    return 0;
  j = index_table[i].start;                  //j等于块范围的起始值
  while (j <= index_table[i].end&&a[j] != key)  //在确定的块内进行查找
    j++;
  if (j>index_table[i].end)    //如果大于块范围的结束值,则说明没有要查找的数
    j = 0;
  return j;
}

int main(int argc, char *argv[])
{
   
  int x, y = 0,ref = 0;
  int key = 8;
  int Array[16] = {
    1, 3, 4, 5, 6, 7, 8, 9, 0, 4, 3, 5, 6, 7, 8, 9 };

  for (x = 1; x <= 3; x++)
  {
   
    index_table[x].start = y + 1;       // 确定每个范围的起始行
    y = y + 1;
    index_table[x].end = y + 4;         // 确定每个块范围的结束值
    y = y + 4;
    index_table[x].key = Array[y];      // 确定每个块范围中元素的最大值
  }

  ref = block_search(key, Array);
  if (ref != 0)
  {
   
    printf("position is: %d \n", ref);
  }
  return 0;
}
相关文章
|
1天前
|
算法 JavaScript Java
【状态压缩】【动态规划】【C++算法】1125.最小的必要团队
【状态压缩】【动态规划】【C++算法】1125.最小的必要团队
|
1天前
|
算法 测试技术 C++
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
|
1天前
|
机器学习/深度学习 算法 测试技术
【动态规划】【C++算法】2742. 给墙壁刷油漆
【动态规划】【C++算法】2742. 给墙壁刷油漆
|
1天前
|
算法 测试技术 C++
【动态规划】【状态压缩】【C++算法】1815 得到新鲜甜甜圈的最多组数
【动态规划】【状态压缩】【C++算法】1815 得到新鲜甜甜圈的最多组数
|
1天前
|
机器学习/深度学习 算法 测试技术
【动态规划】【C++算法】1563 石子游戏 V
【动态规划】【C++算法】1563 石子游戏 V
|
1天前
|
算法 测试技术 C++
【记忆化搜索】【剪枝】【C++算法】1553吃掉 N 个橘子的最少天数
【记忆化搜索】【剪枝】【C++算法】1553吃掉 N 个橘子的最少天数
|
1天前
|
算法 测试技术 C++
【双指针】【C++算法】1537. 最大得分
【双指针】【C++算法】1537. 最大得分
|
1天前
|
算法 测试技术 C++
【动态规划】【中位数】【C++算法】1478. 安排邮筒
【动态规划】【中位数】【C++算法】1478. 安排邮筒
|
1天前
|
算法 测试技术 C++
【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字
【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字
|
1天前
|
人工智能 移动开发 算法
【动态规划】【C++算法】LeetCoce996正方形数组的数目
【动态规划】【C++算法】LeetCoce996正方形数组的数目

相关产品