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

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

2023-06-26 18:11:11 深夜i -- --

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

在计算机科学中，查找算法是指在一组数据中寻找指定的数据元素。常用的两种查找算法是顺序查找和二分查找。在C++中，我们可以使用数组来实现这两种查找算法。

一、顺序查找

顺序查找又被称为线性查找，是一种最简单、最基本的查找算法。其基本思想是从数组的第一个元素开始逐个比较，直到找到目标元素或数组遍历完毕。

示例代码：


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

这段代码中，arr[]表示待查找的数组，n表示数组中元素的个数，target表示待查找的目标元素。函数首先从数组的第一个元素开始遍历，如果找到目标元素，则返回其在数组中的位置。如果数组遍历完毕还未找到目标元素，则返回-1表示未找到。

二、二分查找

二分查找也被称为折半查找，是一种高效的查找算法。其基本思想是将有序数组分为两个部分，每次比较中间元素与目标元素的大小，缩小查找范围，直到找到目标元素或查找范围为空。

示例代码：


int binarySearch(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;
}

这段代码中，arr[]表示待查找的数组，n表示数组中元素的个数，target表示待查找的目标元素。函数首先将查找范围限定在数组的[left, right]区间内，通过不断缩小查找范围，最终找到目标元素或查找范围为空。其中，mid表示[left, right]区间的中间元素，如果中间元素等于目标元素，则返回其位置；如果中间元素小于目标元素，则在[mid+1, right]区间内继续查找；如果中间元素大于目标元素，则在[left, mid-1]区间内继续查找。

总结：

顺序查找和二分查找是两种常用的查找算法。顺序查找适用于无序数组，时间复杂度为O(n)；二分查找适用于有序数组，时间复杂度为O(log n)。在实际应用中，根据数据的特点选择合适的查找算法可以提高程序的效率。

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

下一篇: C++ 函数头文件

评论区

()

相似文章