21xrx.com
2025-03-26 23:03:55 Wednesday
文章检索 我的文章 写文章
C++查找算法介绍和实现
2023-06-28 11:07:59 深夜i     --     --
C++ 查找算法 介绍 实现

C++是一种广泛使用的编程语言，它拥有众多的数据结构和算法库，其中查找算法是其中之一。

查找算法是指在一个数据集合中查找指定元素的过程。常见的查找算法有线性查找（逐个比较）、二分查找、哈希查找等。

线性查找是最基本的查找算法，它是通过逐个比较来寻找目标元素。它的时间复杂度为O(n)。代码实现如下：

int linear_search(int arr[], int n, int target) {
  for(int i = 0; i < n; i++) {
    if(arr[i] == target)
      return i;
    
  }
  return -1;
}

二分查找则是在有序数据集合中查找目标元素的一种快速查找算法。它的时间复杂度为O(logn)。代码实现如下：

int binary_search(int arr[], int n, int target) {
  int left = 0, right = n - 1;
  while(left <= right) {
    int mid = left + (right - left) / 2;
    if(arr[mid] == target)
      return mid;
     else if(arr[mid] < target) {
      left = mid + 1;
    } else
      right = mid - 1;
    
  }
  return -1;
}

哈希查找则是利用哈希表来进行数据查找的算法。它的时间复杂度为O(1)。代码实现如下：

class HashTable {
private:
  int *table;
  int size;
public:
  HashTable(int table_size) {
    table = new int[table_size];
    size = table_size;
    for(int i = 0; i < size; i++) {
      table[i] = -1;
    }
  }
  void insert(int key) {
    int index = key % size;
    while(table[index] != -1) {
      index = (index + 1) % size;
    }
    table[index] = key;
  }
  int search(int key) {
    int index = key % size;
    while(table[index] != key) {
      index = (index + 1) % size;
      if(table[index] == -1)
        return -1;
      
    }
    return index;
  }
};
int main() {
  HashTable hashtable(10);
  hashtable.insert(15);
  hashtable.insert(28);
  hashtable.insert(39);
  int index = hashtable.search(28);
  if(index == -1) {
    cout << "Key not found\n";
  } else {
    cout << "Key found at index " << index << "\n";
  }
  return 0;
}

总的来说，查找算法是计算机程序设计中很重要的一部分，它为解决实际问题提供了非常实用的工具。在编写程序时，选择正确的查找算法非常重要，因为不同的算法在运行效率上可能有很大差异。因此，学习和掌握不同的查找算法能够帮助程序员更好地解决问题。

  
  

评论区