C++实现顺序查找和二分查找算法 |21xrx.com

C++实现顺序查找和二分查找算法

2023-06-29 05:09:42 深夜i -- --

C++ 顺序查找二分查找算法

在计算机程序设计中，查找算法是常见的一种核心算法。查找算法的作用是在一个集合中搜索一个特定的元素，并返回其索引或位置。C++编程语言中，常用的查找算法有顺序查找和二分查找。

顺序查找是一种最基本的查找算法，也称为线性查找。该算法从集合的第一个元素开始，逐个比较每一个元素，直到找到目标元素或遍历完整个集合。顺序查找算法的时间复杂度为O(n)，其中n为集合的大小。

下面是一个使用C++编写的顺序查找算法示例：


#include<iostream>
using namespace std;
int sequential_search(int arr[], int n, int key){
  for (int i = 0; i < n; ++i){
    if (arr[i] == key)
      return i;
  }
  return -1;
}
int main(){
  int arr[] = 9;
  int n = sizeof(arr) / sizeof(arr[0]);
  int key = 5;
  int index = sequential_search(arr, n, key);
  if (index == -1)
    cout << "元素不存在！" << endl;
  else
    cout << "元素存在，位置为：" << index << endl;
  return 0;
}

二分查找是一种更高效的查找算法，也称为折半查找。该算法是基于有序集合的特性，通过比较中间元素和目标元素的大小关系来缩小查找范围，直到找到目标元素或查找范围为空。二分查找算法的时间复杂度为O(logn)，其中n为集合的大小。

下面是一个使用C++编写的二分查找算法示例：


#include<iostream>
using namespace std;
int binary_search(int arr[], int low, int high, int key){
  while (low <= high){
    int mid = (low + high) / 2;
    if (arr[mid] == key)
      return mid;
    else if (arr[mid] < key)
      low = mid + 1;
    else
      high = mid - 1;
  }
  return -1;
}
int main(){
  int arr[] = 4;
  int n = sizeof(arr) / sizeof(arr[0]);
  int key = 5;
  int index = binary_search(arr, 0, n - 1, key);
  if (index == -1)
    cout << "元素不存在！" << endl;
  else
    cout << "元素存在，位置为：" << index << endl;
  return 0;
}

总结来说，顺序查找算法适用于集合大小较小的情况；二分查找算法适用于有序集合且集合大小较大的情况。在实际应用中，我们需要结合集合特性和目标要求来选择合适的查找算法。

上一篇: idea打包java可执行jar包

下一篇: "C++与汇编的结合"

评论区

()

相似文章