21xrx.com
2025-07-12 06:35:02 Saturday
文章检索 我的文章 写文章
C++实现给定数的二分查找
2023-07-05 05:29:29 深夜i     14     0
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++ 中实现给定数的二分查找。

  
  

评论区