21xrx.com
2024-12-23 00:28:02 Monday
登录
文章检索 我的文章 写文章
C++二分查找算法实现
2023-07-06 09:32:38 深夜i     --     --
C++ 二分查找 算法 实现

C++二分查找算法是一种常见的查找算法,在有序的数据集合中查找指定元素的位置,可以高效的解决大量数据的查找问题。本文将介绍C++二分查找的实现方法。

二分查找算法(Binary Search)又称折半查找,它是一种基于比较的查找算法。它的前提是在有序的数组或者列表里进行查找。其操作过程是在每一个比较中,将待查找的元素与中间项进行比较,如果相同则查找成功,否则根据大小关系确定待查找元素在数组的左半部分还是右半部分,并通过反复压缩左、右边的范围,在较短的时间内找到目标元素。

C++代码实现如下:


#include <iostream>

using namespace std;

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;

}

int main()

{

  int arr[] = 3;

  int n = sizeof(arr) / sizeof(arr[0]);

  int target1 = 5, target2 = 6;

  int index1 = binarySearch(arr, n, target1);

  int index2 = binarySearch(arr, n, target2);

  if (index1 != -1)

    cout << "target1 found at index " << index1 << endl;

  

  else

    cout << "target1 not found" << endl;

  

  if (index2 != -1)

    cout << "target2 found at index " << index2 << endl;

  

  else

    cout << "target2 not found" << endl;

  

  return 0;

}

在这段代码中,`binarySearch`函数是二分查找的主要部分。在函数内部,首先定义了左右两个指针`left`和`right`分别指向数组的首尾。然后通过一个while循环实现不断缩小查找区间的范围,直到查找完整个数组或找到目标元素。

在while循环中,首先通过计算中间索引值(mid)来确定目前查找区间的中间位置,然后根据中间位置的元素与目标元素的大小比较调整查找区间的范围。如果中间元素就是目标元素,则直接返回该位置索引值;如果查找的数比中间位置的数小,则在左半部分继续查找;如果查找的数比中间位置的数大,则在右半部分继续查找。

最后,`main`函数中调用`binarySearch`函数,分别查找是否存在5和6两个数,并输出结果。

总结起来,C++二分查找算法能够快速解决大量数据的查找问题,实现也相对简单,只需要按照上面的代码框架进行编写即可。同时,在实际应用过程中,需要注意有序数组存在等值元素的处理与边界条件的判断等问题,以确保算法的正确性和高效性。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复