C++实现给定数的二分查找 |21xrx.com

C++实现给定数的二分查找

2023-07-05 05:29:29 深夜i -- --

C++ 二分查找给定数

二分查找是一种常用的查找算法，使用该算法可以快速定位到给定数在一个有序数组中的位置。而在 C++ 中，实现给定数的二分查找也是非常方便的。

首先，需要确定二分查找的起始位置和结束位置，即数组的左边界和右边界。通常情况下，左边界为 0，右边界为数组长度减 1。然后，使用一个循环不断缩小左右边界的范围，直到找到目标数为止。在每次循环中，比较待查找数与中间值的大小关系，根据结果更新左右边界的值，以及中间值的计算方法。若待查找数不存在于数组中，则最后返回 -1。

以下为 C++ 实现给定数的二分查找的代码示例：


#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int target) {
  while (left <= right) {
    int mid = (left + right) / 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[] = 1;
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 5;
  int result = binarySearch(arr, 0, n - 1, target);
  if (result == -1)
    cout << "该数不存在于数组中" << endl;
  
  else
    cout << "该数在数组中的位置为：" << result << endl;
  
  return 0;
}

在上述代码中，首先定义了一个名为 binarySearch 的函数，其中参数 arr 为待查找的数组，left 和 right 分别为查找的左右边界，target 为待查找的数。函数中使用 while 循环进行二分查找，不断缩小边界的范围，更新中间值 mid 的值，比较 arr[mid] 与 target 的大小关系，根据结果更新边界的值，直到找到目标数为止，返回目标数的索引。若目标数不存在于数组中，则返回 -1。

在 main 函数中，通过定义一个数组 arr，以及使用 sizeof 操作符求得数组长度 n，再将目标数 target 的值传入 binarySearch 函数中，得到目标数在数组中的索引。最后，根据结果输出“该数不存在于数组中”或“该数在数组中的位置为：”加索引值。

通过以上代码，就可以在 C++ 中实现给定数的二分查找。

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

下一篇: 学习完C++后，学习Python需要多长时间？

评论区

()

相似文章