【LeetCode】33. 搜索旋转排序数组
2023-09-14 09:13:24 时间
0 总结
- 可以确定哪一半儿是有序的。在这个基础上,我们就可以知道target到底在不在这个半儿区间,如果在这个区间,那么在这个区间搜索,如果不在,则可能在另外一半儿中。
1.题目
其实这题挺难的。
2.思想
拿到这道题时,我首先考虑的问题是:
- 找到数组的旋转分界线,然后这样我们就可以还原数组(得到一个有序的数组),然后根据二分查找再来迅速定位。
但问题是:是否有必要找到数组的旋转分界线? 其实是没有必要的。那么有没有其它的方法解决这个问题呢?
传统的二分类中,我们都使用mid
下标处的值作为判断依据,但是那是在一个完全有序的数组中是成立的,如果一个数组并非完全有序,那么还有什么其它的判断方法吗?例如本题中,题目给定的条件是:数组原本是有序的,经过一个旋转操作变成了无序,那么在查找的时候,我们可以知道其实 [left,mid-1],[mid,right]
中必有一个是有序的数组。举个例子:在数组中[6,7,1,2,3,4,5]
,我们枚举任意一个下标的数,都会发现由mid划分成的两个区间满足至少有一个区间是有序的,根据这个特性,我们便可以得到一个复杂版的二分法。再分别在这两个子区间内做分析,问题就迎刃而解。
3.代码
可AC的代码如下:
class Solution:
# 得到
def search(self, nums: List[int], target: int) -> int:
left ,right = 0, len(nums)-1
while(left <= right):
mid = (left + right) // 2
if nums[mid] == target: # 这里先比较就避免了后面两次再比较
return mid
if left == mid:
left = mid+1
continue
# 至少有一端是有序的
# 先判断有几个数,左侧是否有序
if nums[left] <= nums[mid-1]:
if nums[left] <= target and target <=nums[mid-1]: # 在下面这个区间二分查找
right = mid-1
else: # 如果不在这个区间,则可能在另外一半儿
left = mid+1
else : # 右侧有序
if nums[mid] <= target and target <=nums[right]: # 在下面这个区间二分查找
left = mid+1
else: # 如果不在这个区间,则仍在左半儿
right = mid-1
return -1
下面这段代码是我的第一印象想法,
class Solution:
def search(self, nums: List[int], target: int) -> int:
bound_idx = get_bound(nums)
if bound_idx == 0:
else:
def get_bound(self,nums):
idx = 1
if len(nums) > 1 :
if nums[idx] > nums[idx-1]: # 前两个数满足升序
else:
return idx-1 # 直接返回0
nxt = idx << 1 # 左移一位
while(idx < len(nums) and nums[idx] < nums[nxt]):
idx = nxt
# 说明在区间 [idx,nxt] 中是存在一个
return idx # 返回下标
相关文章
- Java实现 LeetCode 669 修剪二叉搜索树(遍历树)
- Java实现 LeetCode 668 乘法表中第k小的数(二分)
- Java实现 LeetCode 538 把二叉搜索树转换为累加树(遍历树)
- Java实现 LeetCode 449 序列化和反序列化二叉搜索树
- Java实现 LeetCode 240 搜索二维矩阵 II(二)
- Java实现 LeetCode 173 二叉搜索树迭代器
- Java实现 LeetCode 79 单词搜索
- Java实现 LeetCode 33 搜索旋转排序数组
- Java实现 LeetCode 16 最接近的三数之和
- 【二叉搜索树】LeetCode 98. 验证二叉搜索树【中等】
- LeetCode(98): 验证二叉搜索树
- LeetCode-2347. 最好的扑克手牌【哈希表,计数】
- LeetCode-385. 迷你语法分析器【深度优先搜索,栈】
- ( “树” 之 BST) 108. 将有序数组转换为二叉搜索树 ——【Leetcode每日一题】
- [LeetCode] 74. 搜索二维矩阵 ☆☆☆(二分查找)
- [LeetCode] 33. 搜索旋转排序数组 ☆☆☆(二分查找)
- 【Leetcode刷题Python】40. 组合总和 II
- LeetCode 700. 二叉搜索树中的搜索