21xrx.com
2024-09-20 01:01:24 Friday
登录
文章检索 我的文章 写文章
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++ 实现二分查找的基本思路和代码。相信通过这个例子的介绍,大家对于二分查找这种高效算法能够有更加深刻的理解和应用。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复