C++语言下的二分查找算法 |21xrx.com

C++语言下的二分查找算法

2023-06-22 04:11:40 深夜i -- --

C++语言二分查找算法数组有序时间复杂度

二分查找算法，也叫折半查找法，是一种高效的查找算法。在C++语言中，二分查找算法的实现十分简单，可以用递归或迭代两种方式来实现。

二分查找算法的思路是，先将数组按照升序或降序排列好，然后在中间位置进行查找，如果查找的数比中间位置的数大，则在右半部分查找，反之，则在左半部分查找，直到找到目标数或者查找范围被缩小到只包含一个数为止。

下面是使用递归方式实现的C++代码示例：


int binary_search(int arr[], int low, int high, int target)
{
  if (low > high)
    return -1; // 没有找到目标数，返回-1
  
  int mid = (low + high) / 2; // 计算中间位置
  if (arr[mid] == target)
    return mid; // 找到目标数，返回下标
  
  if (arr[mid] > target)
    return binary_search(arr, low, mid - 1, target); // 在左半部分查找
  
  return binary_search(arr, mid + 1, high, target); // 在右半部分查找
}

上述代码中，变量arr表示要查找的数组，low和high表示查找范围的下标范围，target表示要查找的目标数。函数返回目标数在数组中的下标，如果没有找到则返回-1。

下面是使用迭代方式实现的C++代码示例：


int binary_search(int arr[], int size, int target)
{
  int low = 0, high = size - 1;
  while (low <= high)
  {
    int mid = (low + high) / 2; // 计算中间位置
    if (arr[mid] == target)
      return mid; // 找到目标数，返回下标
    if (arr[mid] > target)
      high = mid - 1; // 在左半部分查找
    else
      low = mid + 1; // 在右半部分查找
  }
  
  return -1; // 没有找到目标数，返回-1
}

上述代码中，变量size表示数组的长度。函数返回目标数在数组中的下标，如果没有找到则返回-1。

总的来说，二分查找算法是一种快速且高效的查找算法，在实际开发中得到广泛的应用。C++语言下的二分查找算法可以使用递归或迭代两种方式来实现。无论是哪种方式，开发者都需要注意参数的传递和算法的实现细节，以保证程序的正确性和效率。

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

下一篇: C++实现多个多媒体计时器的创建

评论区

()

相似文章