在計算機科學(xué)中，搜索算法是一種用于在數(shù)據(jù)集合中查找特定元素的算法。C語言作為一種強大的編程語言，提供了多種搜索算法的實現(xiàn)方式。本文將介紹C語言中的四種常見搜索算法其中包括（線性查找，二分法查找，樹結(jié)構(gòu)查找，分塊查找），并提供每種算法的簡單實現(xiàn)示例。

常見的查找算法主要有以下幾種：

線性查找（Linear Search）：

• 簡單直觀，適用于無序列表。
• 從列表的一端開始逐個元素比較，直到找到目標(biāo)元素或遍歷完整個列表。

二分查找（Binary Search）：

• 適用于有序列表。
• 每次將目標(biāo)值與中間元素比較，可以迅速縮小搜索范圍。

樹結(jié)構(gòu)查找（樹的各種形式，如二叉搜索樹、AVL樹、紅黑樹等）：

• 通過樹結(jié)構(gòu)，可以更加高效地進行查找、插入和刪除操作。
• 二叉搜索樹要求左子樹上所有結(jié)點的值小于根結(jié)點的值，右子樹上所有結(jié)點的值大于根結(jié)點的值。

分塊查找（Block Search）：

• 將數(shù)據(jù)分成若干塊，每一塊中的元素?zé)o序，但塊與塊之間有序。
• 先確定目標(biāo)元素所在的塊，再在塊內(nèi)進行線性查找。

這些查找算法各自有適用的場景和優(yōu)勢，選擇合適的查找算法取決于數(shù)據(jù)的特性以及實際應(yīng)用的需求。

線性查找（Linear Search）

線性搜索，又稱為順序搜索（Sequential Search），是一種簡單直觀的查找算法。該算法通過順序遍歷數(shù)據(jù)集，逐一比較每個元素與目標(biāo)值是否相等，直到找到目標(biāo)值或遍歷完整個數(shù)據(jù)集。

算法步驟

• 從頭到尾遍歷數(shù)據(jù)集： 從數(shù)據(jù)集的第一個元素開始，依次比較每個元素與目標(biāo)值是否相等。
• 比較目標(biāo)值： 對于每個元素，與目標(biāo)值進行比較。
• 找到目標(biāo)值： 如果找到了與目標(biāo)值相等的元素，返回該元素的位置或索引。
• 遍歷完整個數(shù)據(jù)集： 如果遍歷完整個數(shù)據(jù)集仍未找到目標(biāo)值，返回未找到的標(biāo)記（通常是一個特殊值，如-1）。

特點

• 適用于小型數(shù)據(jù)集： 線性搜索適用于小型數(shù)據(jù)集，對于大型數(shù)據(jù)集可能效率較低。
• 無序數(shù)據(jù)： 不依賴數(shù)據(jù)的排列順序，適用于無序數(shù)據(jù)。
• 簡單直觀： 實現(xiàn)簡單，易于理解。

線性搜索是最簡單的搜索算法之一，它按順序遍歷數(shù)據(jù)集合，查找目標(biāo)元素。以下是一個線性搜索的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）是一種在有序數(shù)組中查找目標(biāo)值的算法。它通過反復(fù)將查找范圍劃分為兩半并比較目標(biāo)值與中間元素的大小，從而縮小搜索范圍，直到找到目標(biāo)值或確定目標(biāo)值不存在。

算法步驟

初始化： 確定搜索范圍的起始點 left 和終止點 right。

循環(huán)條件： 當(dāng) left 小于等于 right 時執(zhí)行循環(huán)。

計算中間位置： 計算中間位置 mid，mid = (left + right) / 2。

比較目標(biāo)值： 將目標(biāo)值與中間元素進行比較。

• 如果目標(biāo)值等于中間元素，找到目標(biāo)，返回索引。
• 如果目標(biāo)值小于中間元素，說明目標(biāo)值在左半部分，更新 right = mid - 1。
• 如果目標(biāo)值大于中間元素，說明目標(biāo)值在右半部分，更新 left = mid + 1。

循環(huán)結(jié)束： 當(dāng) left 大于 right，表示搜索范圍為空，未找到目標(biāo)值。

特點

• 有序數(shù)組： 二分搜索要求數(shù)組是有序的，以便通過比較中間元素確定目標(biāo)值在哪一半。
• 高效性： 由于每一步都將搜索范圍縮小一半，因此二分搜索的平均時間復(fù)雜度為 O(log n)。
• 適用性： 適用于靜態(tài)數(shù)據(jù)集或很少變化的數(shù)據(jù)集，不適用于頻繁插入、刪除操作的動態(tài)數(shù)據(jù)集。

二分搜索要求數(shù)據(jù)集合是有序的，以下是一個二分搜索的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++;                    // 記錄查找次數(shù)
    mid = (low + high) / 2;     // 求出中間位置
    if (key<a[mid])             // 當(dāng)key小于中間值
      high = mid - 1;         // 確定左子表范圍
    else if (key>a[mid])        // 當(dāng)key大于中間值
      low = mid + 1;          // 確定右子表范圍
    else if (key == a[mid])     // 當(dāng)key等于中間值證明查找成功
    {
      printf("查找元素: %d Array[%d]=%d\n", count, mid, key);
      count1++;            //count1記錄查找成功次數(shù)
      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）是一種二叉樹數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點都有一個鍵值，且滿足以下性質(zhì)：

• 對于樹中的每個節(jié)點，其左子樹中的所有節(jié)點的鍵值都小于該節(jié)點的鍵值。
• 對于樹中的每個節(jié)點，其右子樹中的所有節(jié)點的鍵值都大于該節(jié)點的鍵值。
• 左、右子樹也分別為二叉搜索樹。

這個性質(zhì)使得在二叉搜索樹中可以高效地進行搜索、插入和刪除操作。

特點

有序性： 由于BST的定義，其中的元素是有序排列的。對于任意節(jié)點，其左子樹的值小于該節(jié)點，右子樹的值大于該節(jié)點，因此通過中序遍歷BST可以得到有序的元素序列。

高效的搜索操作： 由于有序性，可以通過比較鍵值快速定位目標(biāo)節(jié)點，使搜索操作的平均時間復(fù)雜度為 O(log n)。在最壞情況下（樹退化為鏈表），搜索的時間復(fù)雜度為 O(n)。

高效的插入和刪除操作： 插入和刪除操作也涉及到比較鍵值和調(diào)整樹的結(jié)構(gòu)，平均情況下的時間復(fù)雜度為 O(log n)。在最壞情況下，樹可能變得不平衡，導(dǎo)致時間復(fù)雜度為 O(n)，但通過平衡二叉搜索樹（如 AVL 樹、紅黑樹等）可以保持樹的平衡。

操作

搜索（Search）： 從根節(jié)點開始比較目標(biāo)值，根據(jù)比較結(jié)果選擇左子樹或右子樹，直到找到目標(biāo)節(jié)點或達(dá)到葉子節(jié)點。

插入（Insert）： 從根節(jié)點開始，按照比較結(jié)果選擇左子樹或右子樹，直到找到合適的插入位置，插入新節(jié)點。

刪除（Delete）： 找到要刪除的節(jié)點，可能有以下幾種情況：

• 若該節(jié)點為葉子節(jié)點，直接刪除。
• 若該節(jié)點有一個子節(jié)點，用子節(jié)點替代該節(jié)點。
• 若該節(jié)點有兩個子節(jié)點，找到右子樹中的最小節(jié)點或左子樹中的最大節(jié)點，替代該節(jié)點，并遞歸刪除被替代的節(jié)點。

以下是一個簡化的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' 上執(zhí)行BST操作
    return 0;
}

分塊查找（Block Search）

分塊搜索（Block Search）是一種在查找大量數(shù)據(jù)中的目標(biāo)值時，將數(shù)據(jù)分成若干塊，然后在塊內(nèi)進行查找的策略。這種方法適用于一些動態(tài)更新頻繁，但每次更新數(shù)據(jù)量較小的場景。

算法步驟

數(shù)據(jù)分塊： 將大量數(shù)據(jù)按照一定的規(guī)則分成若干塊。

建立索引表： 對每個塊建立索引，記錄每塊的起始位置、結(jié)束位置和關(guān)鍵字（通常是塊內(nèi)最大的關(guān)鍵字）。

查找塊： 根據(jù)目標(biāo)值的大小確定它可能在哪個塊中，找到相應(yīng)的塊。

在塊內(nèi)查找： 在確定的塊內(nèi)使用線性查找或其他查找算法尋找目標(biāo)值。

特點

• 適用于動態(tài)數(shù)據(jù)： 分塊搜索適用于數(shù)據(jù)集動態(tài)更新的情況，因為每次更新數(shù)據(jù)只需更新相應(yīng)塊的索引。
• 索引表： 建立索引表有助于快速定位目標(biāo)值可能存在的塊，提高查找效率。
• 非均勻分塊： 可以根據(jù)數(shù)據(jù)的特點進行非均勻分塊，以適應(yīng)不同數(shù)據(jù)分布情況。

該查找與二分查找類似，都是對半分，分塊則可以分為多塊，效率更高一些。如下這段C語言代碼實現(xiàn)了分塊查找算法。分塊查找是一種基于塊的數(shù)據(jù)結(jié)構(gòu)的搜索算法，通過將數(shù)據(jù)集劃分為若干塊（或稱為塊），并為每個塊建立一個索引。每個索引記錄了該塊的起始位置、結(jié)束位置以及該塊內(nèi)元素的最大值。

#include <stdio.h>

struct index           //定義塊的結(jié)構(gòu)
{
  int key;
  int start;
  int end;
}index_table[4];       //定義結(jié)構(gòu)體數(shù)組

int block_search(int key, int a[])          //自定義實現(xiàn)分塊查找
{
  int i, j;
  i = 1;
  while (i <= 3 && key>index_table[i].key)      //確定在哪個塊中
    i++;
  if (i>3)                                  //大于分得的塊數(shù)，則返回0
    return 0;
  j = index_table[i].start;                  //j等于塊范圍的起始值
  while (j <= index_table[i].end&&a[j] != key)  //在確定的塊內(nèi)進行查找
    j++;
  if (j>index_table[i].end)    //如果大于塊范圍的結(jié)束值，則說明沒有要查找的數(shù)
    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;         // 確定每個塊范圍的結(jié)束值
    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;
}

以上就是C/C++中四種常用查找算法的實現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++查找算法的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論