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

C++实现二分查找算法

2023-06-24 01:25:57 深夜i -- --

C++ 二分查找算法

二分查找算法是一种高效的查找方法，特别适用于有序数组或链表记录的数据集合。通过将待查找的值与中间值进行比较，可以将查找范围缩小一半，从而快速地找到需要的值。在C++语言中，二分查找算法可以通过以下步骤实现：

1. 确定待查找的有序数组或链表；

2. 定义变量记录查找范围的开始和结束位置；

3. 通过计算中间位置的索引值，将查找范围缩小一半；

4. 将待查找的值与中间值进行比较，判断需要向左还是向右查找；

5. 如果待查找的值等于中间值，则查找成功，返回该位置的索引值；

6. 如果待查找的值小于中间值，则更新结束位置为中间位置的前一个位置；

7. 如果待查找的值大于中间值，则更新开始位置为中间位置的后一个位置；

8. 重复步骤3至7，直到找到待查找的值或者查找范围为空。

以下是一个简单的C++程序，用于实现二分查找算法：


#include<iostream>
using namespace std;
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 if (arr[mid] > target)
      right = mid - 1;
    
  }
  return -1;
}
int main() {
  int arr[] = 4;
  int target = 10;
  int n = sizeof(arr) / sizeof(arr[0]);
  int result = binarySearch(arr, n, target);
  cout << "目标值的位置为：" << result << endl;
  return 0;
}

在上面的程序中，我们首先定义了一个待查找的数组arr，以及目标值target。然后，我们计算了数组的长度n，以便在调用二分查找函数时使用。接着，我们调用binarySearch函数，并将待查找的数组、数组长度和目标值作为参数传递进去。最后，我们输出查找结果。

通过以上的程序，我们可以看到，C++语言可以非常方便地实现二分查找算法，以快速地查找出需要的值。如果你在开发中需要对有序数组或链表进行查找，那么二分查找算法将是你的得力助手。

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

下一篇: C++中的标识符是否区分大小写？

评论区

()

相似文章