C++中使用二分法查找前驱的方法 |21xrx.com

C++中使用二分法查找前驱的方法

2023-07-10 14:34:18 深夜i -- --

C++ 二分法查找前驱方法

在C++中，查找前驱是指在一个有序数组或向量中，找到一个给定元素的前面的元素。二分法是一种常用的查找前驱的技术，它利用有序数据的特点，将查找范围逐渐缩小，从而达到高效的查找效果。下面我们就来介绍一下C++中使用二分法查找前驱的方法。

首先，我们需要定义一个有序数组或向量。这个数组或向量中的元素需要按照一定的顺序排列，比如从小到大或从大到小。我们以从小到大排列的数组为例，代码如下：


int arr[] = 5;
int size = sizeof(arr) / sizeof(arr[0]);

接下来，我们可以定义一个函数来实现二分查找前驱的方法。这个函数需要接收两个参数：要查找的元素和有序数组或向量。函数首先需要判断输入的数组或向量是否为空，如果为空则说明查找失败，返回-1。然后，函数需要找到比给定元素小的最大值。在每一次二分的过程中，函数需要判断给定元素是否小于等于当前中间值。如果是，说明查找范围应该在当前中间值左边继续查找。如果不是，说明查找范围应该在当前中间值右边继续查找。代码如下：


int binarySearch(int element, int* arr, int size)
{
  int left = 0, right = size - 1;
  int middle, result = -1;
  while (left <= right)
  {
    middle = (left + right) / 2;
    if (arr[middle] < element)
    {
      result = middle;
      left = middle + 1;
    }
    else
    
      right = middle - 1;
    
  }
  return result;
}

这个函数接收一个给定元素，一个有序数组和数组的大小。它使用一个 while 循环来实现二分查找的过程。在查找的过程中，函数维护一个结果变量 result，它表示比给定元素小的最大值。如果在某次二分中，中间值小于给定元素，则将结果变量设置为当前中间值的下标，并在右半部分继续查找。如果中间值不小于给定元素，则在左半部分继续查找。

最后，我们可以调用这个函数来查找任意给定元素的前驱。比如，在上面的例子中，如果我们要查找元素4的前驱，可以使用下面的代码：


int element = 4;
int pos = binarySearch(element, arr, size);
if (pos >= 0)
{
  cout << "The predecessor of " << element << " is " << arr[pos] << endl;
}
else
  cout << "The predecessor of " << element << " cannot be found!" << endl;

这个代码会输出元素4的前驱3。如果要查找不存在的元素的前驱，函数返回-1，表示查找失败。

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

下一篇: C++字符串长度函数的实现

评论区

()

相似文章