Search algorithm and application examples in C++

Search algorithm and application examples in C

In C, the search algorithm refers to the algorithm for finding specific elements in a set of data. It is one of the most basic and commonly used algorithms in computer programs and is widely used in various practical problems. This article will introduce several search algorithms commonly used in C and give corresponding application examples to help readers better understand and master these algorithms.

1. Linear search algorithm

Linear search algorithm (also called sequential search algorithm) is the simplest and most basic search algorithm. Its basic idea is to compare one by one starting from the first element of the data until the target element is found. The following is the code to implement linear search in C:

int linearSearch(int arr[], int n, int x)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == x)
        {
            return i;   // 找到目标元素返回其下标
        }
    }
    return -1;  // 未找到目标元素返回 -1
}

The time complexity of the linear search algorithm is O(n), where n represents the size of the data, that is, the number of elements in the data. If the element to be found happens to be at the last position in the data, then the linear search needs to traverse the entire data to find the target element, and the time complexity will reach O(n) in the worst case. Therefore, linear search algorithms are not efficient when the data size is large.

2. Binary search algorithm

The binary search algorithm (also known as the binary search algorithm) is an efficient search algorithm. It requires that the data must be in order, and reduces the scope of the search by half in each search, and finally finds the target element. The following is the code to implement binary search in C:

int binarySearch(int arr[], int n, int x)
{
    int left = 0, right = n - 1, mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] == x)
        {
            return mid;   // 找到目标元素返回其下标
        }
        else if (arr[mid] > x)
        {
            right = mid - 1;   // 目标元素在左边区域
        }
        else
        {
            left = mid + 1;   // 目标元素在右边区域
        }
    }
    return -1;  // 未找到目标元素返回 -1
}

The time complexity of the binary search algorithm is O(log n), where n represents the size of the data, that is, the number of elements in the data. The binary search algorithm takes advantage of the characteristics of ordered data. Each search can halve the search range to quickly find the target element. However, when the data is not sorted, it needs to be sorted before binary search can be used, which will add additional time complexity.

3. Hash search algorithm

The hash search algorithm (also called hash search algorithm) is an algorithm that uses a hash function to quickly search. It quickly finds the target element by mapping the data element to a fixed position (i.e., hash value). The following is the code to implement hash search in C:

const int MAX_SIZE = 10007;   // 哈希表的最大长度

struct Node
{
    int key, value;   // 哈希表中存放的元素
    Node* next;   // 指向下一个节点的指针
};

class HashTable
{
private:
    Node* table[MAX_SIZE];   // 哈希表的数组
    int hashFunc(int key) { return key % MAX_SIZE; }   // 哈希函数

public:
    HashTable() { memset(table, 0, sizeof(table)); }   // 初始化哈希表

    void insert(int key, int value)   // 将元素插入哈希表
    {
        int pos = hashFunc(key);
        Node* p = new Node();
        p->key = key;
        p->value = value;
        p->next = table[pos];
        table[pos] = p;
    }

    int search(int key)   // 在哈希表中查找元素
    {
        int pos = hashFunc(key);
        Node* p = table[pos];
        while (p != NULL)
        {
            if (p->key == key)
            {
                return p->value;   // 找到目标元素返回其值
            }
            p = p->next;
        }
        return -1;  // 未找到目标元素返回 -1
    }
};

The time complexity of the hash search algorithm is O(1), which is not affected by the size of the data and is very efficient. However, there are many factors that need to be considered in the design of the hash function. If the hash function is not good, it may cause hash conflicts, thus affecting the search efficiency.

4. Application examples of search algorithms

In addition to the above three search algorithms, there are many other search algorithms in C, such as interpolation search, Fibonacci search, etc. A simple application example is given below to show the application of the search algorithm in practical problems.

Given an array and a target value, find the sum of two numbers in the array equal to the target value, and return the subscripts of the two numbers. The following is the code to implement this function in C:

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> umap;
    int size = nums.size();
    for (int i = 0; i < size; i++)
    {
        int complement = target - nums[i];
        if (umap.find(complement) != umap.end())
        {
            return { umap[complement], i };
        }
        umap[nums[i]] = i;
    }
    return {};
}

This algorithm uses the idea of ​​hash search. During the process of traversing the array, it searches in the hash table whether there is a target value added to the current element. elements, returning their indexes if they exist.

Summary

This article introduces three search algorithms commonly used in C: linear search algorithm, binary search algorithm and hash search algorithm, and gives corresponding application examples. Understanding the advantages, disadvantages and practical applications of these search algorithms can help us use them better in programming and improve the efficiency and quality of the program.

The above is the detailed content of Search algorithm and application examples in C++. For more information, please follow other related articles on the PHP Chinese website!