首页 > 试题广场 >

在有序旋转数组中找到一个数

[编程题]在有序旋转数组中找到一个数

有序数组arr可能经过一次旋转处理，也可能没有，且arr可能存在重复的数。例如，有序数组[1, 2, 3, 4, 5, 6, 7]，可以旋转处理成[4, 5, 6, 7, 1, 2, 3]等。给定一个可能旋转过的有序数组arr，再给定一个数num，返回arr中是否含有num

关于旋转操作：可以简单的理解为把序列从某个位置切成两段然后交换位置

[要求]

期望复杂度为 $O(\log n)$

第一行两个整数N, num。分别表示数组大小, 需要找的数。
接下来一行N个整数表示数组内的数。

若num存在于数组中，输出"Yes"，否则输出"No"

示例1

输入

7 7
4 5 6  7 1 2 3

Yes

示例2

7 998244353
4 5 6  7 1 2 3

No

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

分治

上传者：小小

难度：

0条回答 11收藏 4051浏览

查看代码

在有序旋转数组中找到一个数

扫一扫，把题目装进口袋