C++实例：二分查找题解 |21xrx.com

C++实例：二分查找题解

2023-06-23 10:07:02 深夜i -- --

C++ 实例二分查找题解

二分查找是一种十分高效的查找算法，因为它的时间复杂度是 O(log n)，而不是 O(n)。

二分查找的实现方法就是不断地将查找范围缩小一半，直到找到要查找的元素或者确定元素不存在为止。

在 C++ 中，实现二分查找非常简单。下面我们就来看一个例子。

题目描述：

在一个有序序列中，查找一个元素是否存在。如果存在，则返回元素的位置；如果不存在，则返回 -1。

思路：

1.通过二分法可以将查找区间每次缩小一半，直到查找区间中不存在元素为止。

2.首先设定左右指针，分别指向序列数组的起始位置和终止位置。

3.然后通过循环的方式，不断缩小查找区间。

4.每次循环都通过取中间位置，将查找区间分为左右两部分。

5.接着，判断中间位置的值和要查找的值的大小关系。

6.如果相等，则返回中间位置的下标。

7.如果中间位置的值大于要查找的值，则更新右指针为中间位置减一。

8.如果中间位置的值小于要查找的值，则更新左指针为中间位置加一。

9.当左右指针相遇时，如果相遇位置的值等于要查找的值，则返回该位置的下标，否则返回 -1。

代码实现：


int binary_search(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)
      right = mid - 1;
    else
      left = mid + 1;
  }
  return -1;
}

以上就是关于 C++ 实现二分查找的基本思路和代码。相信通过这个例子的介绍，大家对于二分查找这种高效算法能够有更加深刻的理解和应用。

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

下一篇: C++程序代码大全

评论区

()

相似文章