Implementation of four commonly used search algorithms in C/C++

In computer science, a search algorithm is an algorithm used to find specific elements in a data set. As a powerful programming language, C language provides multiple ways to implement search algorithms. This article will introduce four common search algorithms in C language, including (linear search, dichotomous search, tree structure search, chunked search), and provide simple implementation examples of each algorithm.

There are several common search algorithms:

Linear Search:

Simple and intuitive, suitable for unordered lists.
Start by element comparison from one end of the list until the target element is found or the full list is traversed.

Binary Search:

Suitable for ordered lists.
Each time you compare the target value to the intermediate element, you can quickly narrow the search range.

Tree structure search (various forms of trees, such as binary search trees, AVL trees, red and black trees, etc.):

Through the tree structure, you can search, insert and delete operations more efficiently.
The binary search tree requires that the values of all nodes on the left subtree are smaller than the values of the root node, and the values of all nodes on the right subtree are larger than the values of the root node.

Block Search:

Divide the data into several blocks, the elements in each block are out of order, but the blocks are ordered.
First determine the block where the target element is located, and then perform linear searches within the block.

These search algorithms each have their own applicable scenarios and advantages. The choice of the appropriate search algorithm depends on the characteristics of the data and the needs of actual application.

Linear Search

Linear search, also known as Sequential Search, is a simple and intuitive search algorithm. The algorithm traverses the dataset sequentially, comparing whether each element is equal to the target value one by one until the target value is found or the complete dataset is traversed.

Algorithm steps

Iterate through the dataset from beginning to end:Starting from the first element of the dataset, compare whether each element is equal to the target value in turn.
Compare the target values:For each element, compare with the target value.
Find the target value:If an element equal to the target value is found, return the position or index of the element.
Iterate through the complete dataset:If the target value is not found through the complete dataset, return the unfound mark (usually a special value, such as -1).

Features

Suitable for small datasets:Linear search is suitable for small data sets and may be inefficient for large data sets.
Unordered data:It does not depend on the order of data arrangement and is suitable for unordered data.
Simple and intuitive:Simple implementation and easy to understand.

Linear search is one of the easiest search algorithms that it traverses the data collection in order to find target elements. Here is an example of a linear search in C language:

#include &lt;&gt;

int linearSearch(int arr[], int n, int target)
{
    for (int i = 0; i &lt; n; i++)
    {
        if (arr[i] == target)
        {
            return i; // If found, return the index        }
    }
    return -1; // If not found, return -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("Element found at index %d\n", result);
    } else
    {
        printf("Element not found\n");
    }
    return 0;
}

Binary Search

Binary Search is an algorithm for finding target values in an ordered array. It narrows the search range by repeatedly dividing the search range into two halves and comparing the size of the target value to the intermediate element until the target value is found or determined that the target value does not exist.

Algorithm steps

initialization:Determine the starting point of the search rangeleftand the end pointright。

Cycle conditions:whenleftLess than or equal torightExecute loop when .

Calculate the intermediate position:Calculate the intermediate positionmid，mid = (left + right) / 2。

Compare the target values:Compare the target value to the intermediate element.

If the target value is equal to the intermediate element, find the target and return the index.
If the target value is less than the middle element, it means that the target value is in the left half, updateright = mid - 1。
If the target value is greater than the middle element, it means that the target value is in the right half, updateleft = mid + 1。

End of the loop:whenleftGreater thanright, means that the search range is empty and the target value is not found.

Features

Ordered array:Binary search requires that the array is ordered so that the target value is determined by comparing the intermediate elements.
Efficiency:Since each step reduces the search range by half, the average time complexity of binary search is O(log n).
applicability:Applicable to static data sets or data sets with little change, and not to dynamic data sets with frequent insertion and deletion operations.

Binary search requires that the data set is ordered. The following is a C language example of binary search:

#include &lt;&gt;

int binary_search(int key, int a[], int n)
{
  int low, high, mid, count = 0, count1 = 0;
  low = 0;
  high = n - 1;
  while (low&lt;high)
  {
    count++;                    // Record the number of searches    mid = (low + high) / 2;     // Find the intermediate position    if (key&lt;a[mid])             // When the key is less than the intermediate value      high = mid - 1;         // Determine the left subtable range    else if (key&gt;a[mid])        // When the key is greater than the intermediate value      low = mid + 1;          // Determine the right subtable range    else if (key == a[mid])     // When key equals the intermediate value, it proves that the search is successful    {
      printf("Find elements: %d Array[%d]=%d\n", count, mid, key);
      count1++;            //count1 record number of successful searches      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;
}

Binary Search Tree (BST)

Binary Search Tree (BST) is a binary tree data structure in which each node has a key value and meets the following properties:

For each node in the tree, the key values of all nodes in its left subtree are smaller than the key values of that node.
For each node in the tree, the key values of all nodes in its right subtree are greater than the key values of that node.
The left and right subtrees are also binary search trees respectively.

This property enables efficient search, insert and delete operations in the binary search tree.

Features

Order:Due to the definition of BST, the elements in it are arranged in an orderly manner. For any node, the value of its left subtree is smaller than that node and the value of the right subtree is larger than that node. Therefore, an ordered sequence of elements can be obtained by traversing the BST in the middle order.

Efficient search operations:Due to orderliness, the target node can be quickly positioned by comparing key values, so that the average time complexity of the search operation is O(log n). In the worst case (the tree degenerates into a linked list), the time complexity of the search is O(n).

Efficient insertion and deletion operations:The insertion and deletion operations also involve comparing key values and adjusting the structure of the tree. The time complexity in the average case is O(log n). In the worst case, the tree may become unbalanced, resulting in a time complexity of O(n), but the equilibrium of the tree can be maintained by balancing binary search trees (such as AVL trees, red and black trees, etc.).

operate

Search:Start comparing the target value from the root node, and select the left subtree or right subtree according to the comparison results until the target node is found or the leaf node is reached.

Insert:Starting from the root node, select the left subtree or right subtree according to the comparison results until you find the appropriate insertion position and insert the new node.

Delete:When finding the node to be deleted, there may be the following situations:

If this node is a leaf node, delete it directly.
If the node has a child node, replace the node with the child node.
If the node has two child nodes, find the smallest node in the right subtree or the largest node in the left subtree, replace the node, and recursively delete the replaced node.

Here is a simplified C example of BST:

#include &lt;&gt;
#include &lt;&gt;

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

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

struct Node* insert(struct Node* root, int key)
{
    if (root == NULL)
        return newNode(key);
    if (key &lt; root-&gt;key)
        root-&gt;left = insert(root-&gt;left, key);
    else if (key &gt; root-&gt;key)
        root-&gt;right = insert(root-&gt;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 &lt; sizeof(keys) / sizeof(keys[0]); i++)
    {
        root = insert(root, keys[i]);
    }
    // BST operation can be performed on 'root'    return 0;
}

Block Search

Block Search is a strategy that divides the data into several blocks when searching for target values in a large amount of data and then searches within the block. This method is suitable for some scenarios where dynamic updates are frequent but the amount of data is small each time.

Algorithm steps

Data chunking:Divide a large amount of data into several blocks according to certain rules.

Create index table:Enter each block and record the start, end position and keyword of each block (usually the largest keyword in the block).

Find blocks:Determine which block it may be in based on the size of the target value and find the corresponding block.

Find within the block:Use linear search or other search algorithms to find the target value within the determined block.

Features

Suitable for dynamic data:Block search is suitable for dynamic updates of data sets, because each update of data only requires updating the index of the corresponding block.
Index table:Establishing an index table helps quickly locate blocks that may exist in the target value and improve search efficiency.
Inhomogeneous chunking:Inhomogeneous blocking can be performed according to the characteristics of the data to adapt to different data distributions.

This search is similar to binary search, both half-parts, and blocks can be divided into multiple blocks, which is more efficient. The following C language code implements a block search algorithm. Block search is a search algorithm based on block-based data structures, which divides the data set into several blocks (or blocks) and creates an index for each block. Each index records the start position, end position of the block, and the maximum value of elements within the block.

#include &lt;&gt;

struct index           //Define the block structure{
  int key;
  int start;
  int end;
}index_table[4];       //Define the structure array
int block_search(int key, int a[])          //Custom implementation of chunking search{
  int i, j;
  i = 1;
  while (i &lt;= 3 &amp;&amp; key&gt;index_table[i].key)      //Determine which block is in    i++;
  if (i&gt;3)                                  //The number of blocks greater than the divided one will return 0    return 0;
  j = index_table[i].start;                  //j is equal to the starting value of the block range  while (j &lt;= index_table[i].end&amp;&amp;a[j] != key)  //Search within the determined block    j++;
  if (j&gt;index_table[i].end)    //If it is greater than the end value of the block range, it means there is no number to be found    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 &lt;= 3; x++)
  {
    index_table[x].start = y + 1;       // Determine the starting line for each range    y = y + 1;
    index_table[x].end = y + 4;         // Determine the end value of each block range    y = y + 4;
    index_table[x].key = Array[y];      // Determine the maximum value of elements in each block range  }

  ref = block_search(key, Array);
  if (ref != 0)
  {
    printf("position is: %d \n", ref);
  }
  return 0;
}

The above is the detailed content of the implementation of four commonly used search algorithms in C/C++. For more information about the search algorithm of C++, please pay attention to my other related articles!