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

C++语言实现二分查找算法

2023-06-29 07:53:12 深夜i -- --

C++ 二分查找算法实现

二分查找算法，也叫折半查找算法，是一种常用的查找算法。它的基本思想是：将有序的数组分成两个部分，如果要查找的元素比数组中间的元素小，就在前半部分查找；如果比数组中间的元素大，就在后半部分查找，以此类推，直到找到要查找的元素或查找完整个数组。

C++语言是一种高级的、面向对象的编程语言，与二分查找算法结合后，可以快速实现二分查找。

以下是C++代码实现二分查找算法：


#include<iostream>
using namespace std;
//二分查找算法
int binary_search(int* arr, int length, int target) {
  int left = 0, right = length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target)
      return mid;
     else if (arr[mid] > target)
      right = mid - 1;
     else {
      left = mid + 1;
    }
  }
  return -1;
}
int main() {
  int arr[] = 17;
  int length = sizeof(arr) / sizeof(arr[0]);
  int target = 11;
  int result = binary_search(arr, length, target);
  if (result == -1)
    cout<<"Not found"<<endl;
   else
    cout<<"Found "<<target<<" at index "<<result<<endl;
  
  return 0;
}

在上述代码中，我们首先定义了一个int类型的数组arr，并给出了数组元素的值。然后，我们通过数组的长度确定了右边界right，也就是数组最后一个元素的下标值。

接着，我们定义了一个函数binary_search，该函数接收三个参数：指向数组开头的指针、数组长度以及要查找的目标值。在函数中，我们定义了left和right两个变量，分别表示查找的区间的左边界和右边界。

接下来，我们使用while循环，通过对left和right的不断调整来缩小查找的范围。在每次循环中，我们使用mid变量表示当前的中间位置，并将其与目标值进行比较，从而判断目标值在左半部分还是右半部分。如果目标值小于中间值，则我们在查找区间的左半部分查找；如果目标值大于中间值，则在右半部分查找。如果mid表示的值与target相等，则表示找到了目标元素，我们返回mid的值。如果left>right，则表示没有找到目标元素，返回-1即可。

最后，在主函数中我们使用binary_search函数查找元素11在数组arr中的位置，并输出查找结果。

总的来说，二分查找算法是一种高效的查找算法，能够快速地查找有序数组中的元素，结合C++语言的特点，可以很容易地实现二分查找算法。

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

下一篇: C++中gets函数的使用说明

评论区

()

相似文章