在一个已排序且旋转的数组中搜索元素的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中文网其他相关文章!

热AI工具

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

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

热门话题

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

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

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

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

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

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

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

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