C++实现二分法算法 |21xrx.com

C++实现二分法算法

2023-07-05 10:44:54 深夜i -- --

C++ 二分法算法实现

二分法算法是一种高效的搜索算法，常用于有序数组的查找操作。在C++中，我们可以使用循环结构或递归函数来实现二分法算法。

假设我们要在一个有序数组中查找某个特定的值，我们首先需要确定查找范围。假设数组为arr，长度为n，我们将查找范围设定为[left, right]，其中left为数组的第一个元素索引值，right为数组的最后一个元素索引值。

循环实现

假设我们要查找的值为target，我们可以使用如下的循环结构来实现二分法算法：


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;
}

首先，我们将查找范围设定为[left, right]。接下来，我们在while循环结构中不断缩小查找范围，直到找到目标为止。在每次循环中，我们计算mid的值，其中mid为[left, right]区间的中间元素。如果arr[mid]等于目标值，则已找到目标，返回mid的值即可。如果arr[mid]小于目标值，则目标值只可能在[mid+1, right]区间内。因此，我们将left的值更新为mid+1。如果arr[mid]大于目标值，则目标值只可能在[left, mid-1]区间内。因此，我们将right的值更新为mid-1。

递归实现

我们也可以使用递归函数来实现二分法算法。如下所示：


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

在递归函数中，我们首先需要判断查找范围是否有效。如果left > right，则说明查找范围为空，目标值不存在于数组中。如果arr[mid]等于目标值，则已找到目标，返回mid的值即可。如果arr[mid]小于目标值，则目标值只可能在[mid+1, right]区间内。因此，我们将查找范围更新为[mid+1, right]，调用递归函数。如果arr[mid]大于目标值，则目标值只可能在[left, mid-1]区间内。因此，我们将查找范围更新为[left, mid-1]，调用递归函数。

总结

无论是循环结构还是递归函数，实现二分法算法的核心思想是不断缩小查找范围，直到找到目标为止。在实际编程中，我们需要确保数组是有序的，并根据实际情况选择循环结构或递归函数来实现算法。

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

下一篇: Node.js各个版本的安装要求

评论区

()

相似文章