搜索旋转排序数组
2022/8/28 23:28:07
本文主要是介绍搜索旋转排序数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 题目描述
- 解题思路
- 解题代码
题目描述
- 题目地址:https://leetcode.cn/problems/search-in-rotated-sorted-array/
- 题目要求
整数数组nums
按升序排列,数组中的值互不相同 。
在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了旋转,使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如,[0,1,2,4,5,6,7]
在下标 3
处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你旋转后的数组nums和一个整数target,如果nums中存在这个目标值target ,则返回它的下标,否则返回**-1 **。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
解题思路
- 对有序或者部分有序的数组,基本使用二分搜索及其变种
- 最关键的一步就是要找出中间值 const mid = (left + right) >> 1
- 如果中间值大于最左端点,说明左边是升序,否则右边是升序
- 先判断目标值是否在升序里,如果不在,left=mid+1,再去右边查找
解题代码
var search = function(nums, target) { // 二分法 let [left, right] = [0, nums.length - 1]; while (left <= right) { const mid = (left + right) >> 1; if (nums[mid] === target) return mid; if (nums[left] < nums[mid]) { // 左边是升序的 if (nums[left] <= target && target < nums[mid]) { // target在升序的里面 right = mid - 1; } else { // target不在升序的里面 left = mid + 1; } } else { // 右边升序 if (nums[mid] <= target && target <= nums[right]) { // target在升序的里面 left = mid + 1; } else { // target不在升序的里面 right = mid - 1; } } } return -1; };
这篇关于搜索旋转排序数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署