搜索旋转排序数组——好久没有刷题了,核心是分3段处理,最前的升序段,最后的升序段,需要利用A[0],A[-1],A[mid]和target关系。
2023-09-14 09:11:49 时间
62. 搜索旋转排序数组
中文
English
假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7
可能成为4 5 6 7 0 1 2
)。给定一个目标值进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1。你可以假设数组中不存在重复的元素。
样例
例1:
输入: [4, 5, 1, 2, 3] and target=1,
输出: 2.
例2:
输入: [4, 5, 1, 2, 3] and target=0,
输出: -1.
挑战
O(logN) 时间限制
class Solution: """ @param A: an integer rotated sorted array @param target: an integer to be searched @return: an integer """ def search(self, A, target): # write your code here if not A: return -1 l,r = 0,len(A)-1 while l+1 < r: mid = (l+r) >> 1 if A[0] < A[mid]: if A[0] <= target <= A[mid]: r = mid else: l = mid else: if A[mid] <= target <= A[-1]: l = mid else: r = mid if A[l] == target: return l if A[r] == target: return r return -1
相关文章
- 谷歌搜索突发全球性宕机
- uni-app实现搜索跳转功能
- SuperSearch(超级网搜) – 更名为 AllWebSearch《全网搜索 6.0》 – 让思考从搜索开始
- 年会 (记忆化搜索+二叉树思想)------------------------------C语言—菜鸟级
- 【ES三周年】使用AIGC模型智能生成Elasticsearch搜索语句
- 判断数组是否是二叉树搜索树的后序遍历结果
- Power BI模拟谷歌2022搜索排行榜
- 【ES三周年】- ES在电商搜索中的应用实践
- 搜索旋转排序数组
- Django admin ForeignKey 字段增加搜索选择框
- Linux 通配符:强大的文件搜索利器(linux的通配符)
- 谷歌率先在iOS上推出删除最后15分钟搜索历史记录的快捷方式
- Map值增加的最高效的方法:只一次搜索键
- 利用Oracle关键字搜索,提升查询效率(oracle关键字搜索)
- 利用Oracle数据库实现全表搜索(oracle 全表 搜索)
- JavaScript中数组的排序、乱序和搜索实现代码
- 在SQLServer中实现最短路径搜索的解决方法
- ThinkPHP让分页保持搜索状态的方法
- 使用jQuery简单实现模拟浏览器搜索功能
- jquery实现搜索框常见效果的方法