目录
算法
示例
输出
结论
首页 后端开发 C++ 在一个已排序且旋转的数组中搜索元素的C++程序

在一个已排序且旋转的数组中搜索元素的C++程序

Sep 15, 2023 am 09:41 AM
已排序 (sorted) 旋转 (rotated) 搜索元素 (search element)

在一个已排序且旋转的数组中搜索元素的C++程序

我们得到一个围绕一个点旋转的排序数组。我们还获得了一个在数组中搜索的键。在这个旋转数组中搜索元素所采用的逻辑是 -

  • 首先,我们找到数组的中间元素。如果密钥存在,则我们返回该密钥存在于数组中。

  • 如果键不在中间,我们可以查看数组的左侧部分(从左到中)是否已排序。如果已排序,则可以在左侧查找 key,否则可以在右侧(mid+1, right)查找

  • 如果中间没有找到key,并且左边部分没有排序,那么我们会对右边部分进行排序,然后我们可以看看右边部分是否存在该key,或者我们会在右边部分进行搜索数组的左侧

  • 否则我们返回找不到。

让我们看看下面的一些输入输出场景 -

想象有一个由其中的元素组成的数组。例如,2 ,5, 7, 9, 11,旋转后变成了 5, 9, 11, 2, 7。假设数组的键是 2。

Input: arr[] = {5, 9, 11, 2, 7}, Key=2
Output: Element "2" found at 3rd index
登录后复制

让我们假设另一个场景,其中键不在指定的数组中。

Input: arr[] = {10, 23, 45, 77, 84}, Key=90
Output: Element "90" not found.
登录后复制

算法

以下步骤是实现方法。

  • 查找数组的中间元素。

  • 将数组分为两部分。 ( 中 = 左 + 右 ) / 2

  • 检查key是否为中间元素。

  • Else if ,检查数组左侧的元素并且它已排序

  • else if,检查右侧元素(mid+1,right)

  • 否则如果,对左侧部分进行排序并检查

  • 否则,返回未找到的元素。

示例

例如,假设我们有一个数组“2,3,4,5,6,7,8”,旋转后的数组是“5,6,7,8,2,3,4”。该数组的键是2。

该操作的 C++ 实现如下 -

#include <iostream>
#include <vector>
using namespace std;
bool solve(vector<int> arr, int left, int right, int key) {
   if (left > right) {
      return false;
   }
   int mid = (left + right)/2;
   if (arr[mid] == key) {
      return true;
   }
   if (arr[left] <= arr[mid]) {
      if (key >= arr[left] && key <= arr[mid]) {
         return solve(arr, left, mid-1, key);
      }
      return solve(arr, mid+1, right, key);
   }
   if (key >= arr[mid] && key <= arr[right])
      return solve(arr, mid+1, right, key);
   return solve(arr, left, mid-1, key);
}
int main() {
   vector<int> arr = {5, 6, 7, 8, 2, 3, 4};
   int key = 2;
   if(solve(arr, 0, arr.size()-1, key)) cout << key << " is present";
      else cout << key << " is not present";
   return 0;
}
登录后复制

输出

2 is present
登录后复制

结论

解决此问题的另一种方法是找出数组旋转的枢轴点或索引,然后对边进行二分搜索。我们的方法只需要 1 次二分搜索即可解决问题。每当我们看到搜索和排序数组时,我们都应该将二分搜索作为搜索方法之一。

以上是在一个已排序且旋转的数组中搜索元素的C++程序的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

C语言数据结构:树和图的数据表示与操作 C语言数据结构:树和图的数据表示与操作 Apr 04, 2025 am 11:18 AM

C语言数据结构:树和图的数据表示与操作树是一个层次结构的数据结构由节点组成,每个节点包含一个数据元素和指向其子节点的指针二叉树是一种特殊类型的树,其中每个节点最多有两个子节点数据表示structTreeNode{intdata;structTreeNode*left;structTreeNode*right;};操作创建树遍历树(先序、中序、后序)搜索树插入节点删除节点图是一个集合的数据结构,其中的元素是顶点,它们通过边连接在一起边可以是带权或无权的数据表示邻

C语言文件操作难题的幕后真相 C语言文件操作难题的幕后真相 Apr 04, 2025 am 11:24 AM

文件操作难题的真相:文件打开失败:权限不足、路径错误、文件被占用。数据写入失败:缓冲区已满、文件不可写、磁盘空间不足。其他常见问题:文件遍历缓慢、文本文件编码不正确、二进制文件读取错误。

在C中如何有效地使用RVALUE参考? 在C中如何有效地使用RVALUE参考? Mar 18, 2025 pm 03:29 PM

文章讨论了在C中有效使用RVALUE参考,以进行移动语义,完美的转发和资源管理,重点介绍最佳实践和性能改进。(159个字符)

如何在C 20中使用范围进行更有表现的数据操纵? 如何在C 20中使用范围进行更有表现的数据操纵? Mar 17, 2025 pm 12:58 PM

C 20范围通过表现力,合成性和效率增强数据操作。它们简化了复杂的转换并集成到现有代码库中,以提高性能和可维护性。

c语言函数的基本要求有哪些 c语言函数的基本要求有哪些 Apr 03, 2025 pm 10:06 PM

C语言函数是代码模块化和程序搭建的基础。它们由声明(函数头)和定义(函数体)组成。C语言默认使用值传递参数,但也可使用地址传递修改外部变量。函数可以有返回值或无返回值,返回值类型必须与声明一致。函数命名应清晰易懂,使用驼峰或下划线命名法。遵循单一职责原则,保持函数简洁性,以提高可维护性和可读性。

如何使用C中的移动语义来提高性能? 如何使用C中的移动语义来提高性能? Mar 18, 2025 pm 03:27 PM

本文讨论了使用C中的移动语义来通过避免不必要的复制来提高性能。它涵盖了使用std :: Move的实施移动构造函数和任务运算符,并确定了关键方案和陷阱以有效

c上标3下标5怎么算 c上标3下标5算法教程 c上标3下标5怎么算 c上标3下标5算法教程 Apr 03, 2025 pm 10:33 PM

C35 的计算本质上是组合数学,代表从 5 个元素中选择 3 个的组合数,其计算公式为 C53 = 5! / (3! * 2!),可通过循环避免直接计算阶乘以提高效率和避免溢出。另外,理解组合的本质和掌握高效的计算方法对于解决概率统计、密码学、算法设计等领域的许多问题至关重要。

动态调度如何在C中起作用,如何影响性能? 动态调度如何在C中起作用,如何影响性能? Mar 17, 2025 pm 01:08 PM

本文讨论了C中的动态调度,其性能成本和优化策略。它突出了动态调度会影响性能并将其与静态调度进行比较的场景,强调性能和之间的权衡

See all articles