【LeetCode】搜索旋转排序数组 [M](二分)
2023-09-27 14:19:51 时间
一、题目
整数数组 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) 的算法解决此问题。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0 输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3 输出:-1
示例 3:
输入:nums = [1], target = 0 输出:-1
提示:
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- nums 中的每个值都 独一无二
- 题目数据保证 nums 在预先未知的某个下标上进行了旋转
- -10^4 <= target <= 10^4
二、代码
class Solution {
public int search(int[] nums, int target) {
// 设置左右边界指针
int l = 0;
int r = nums.length - 1;
// 开始二分
while (l <= r) {
// 计算中间下标
int m = (l + r) >> 1;
// 如果中间值正好等于target,直接返回下标m
if (nums[m] == target) {
return m;
}
// 如果三个下标位置的数相等,并且他们又不等于target([L] == [M] == [R] != target),这种情况是没有办法二分的,因为无法确定断电在左侧还是在右侧
if (nums[l] == nums[m] && nums[m] == nums[r]) {
// 这种情况下让L往下走,L++,直到遇到一个不是num[M]的位置,在当前L...R上继续二分
while (l != m && nums[l] == nums[m]) {
l++;
}
// 执行到这里,有两种情况:
// 1) L == M L...M都一路都相等
// 2) 从L到M终于找到了一个不等的位置
if (l == m) { // L...M 一路都相等
// L一直往右,到M了,一路都是num[M],那么在M+1到R上二分
l = m + 1;
continue;
}
}
// 执行到这里,arr[M]一定是 != num的
// [L] [M] [R] 不都一样的情况, 如何二分的逻辑
// [L] != [M]
if (nums[l] != nums[m]) {
// 如果[L] < [M],说明左侧是有序的,那么断点应该在右侧
if (nums[l] < nums[m]) {
// 如果target的范围就在左侧有序的范围内,那么我们就对左侧进行二分
if (target >= nums[l] && target < nums[m]) {
r = m - 1;
// 否则,target就应该在无序的右侧,我们就去右侧进行二分
} else {
l = m + 1;
}
// 这个情况就是右侧是有序的,断点在左侧
} else {
// 如果target的范围就在右侧有序的范围内,那么我们就对右侧进行二分
if (target > nums[m] && target <= nums[r]) {
l = m + 1;
// 否则,target就应该在无序的左侧,我们就去左侧进行二分
} else {
r = m - 1;
}
}
// [M] != [R]
} else {
// 如果[M] < [R],说明右侧是有序的,那么断点应该在左侧
if (nums[m] < nums[r]) {
if (target > nums[m] && target <= nums[r]) {
l = m + 1;
} else {
r = m - 1;
}
// 这个情况就是左侧是有序的,断点在右侧
} else {
if (target >= nums[l] && target < nums[m]) {
r = m - 1;
} else {
l = m + 1;
}
}
}
}
// 如果整个二分过程没有找到target,就说明数组中没有target,返回-1
return -1;
}
}
三、解题思路
将数组分成左右两部分,如果[L] < [M],那么说明左部分一定是有序的,断点一定在右侧。反之,如果[M] < [R],那么说明右部分一定是有序的,断点一定在左侧。因为断点所在的那一侧一定会是[L] > [M]或[M] > [R],这一点随便举例子就能发现。
相关文章
- Leetcode: Valid Parentheses
- LeetCode高频题79. 单词搜索,如果 word 存在于网格中,返回 true ;否则,返回 false
- JS Leetcode 33. 搜索旋转排序数组题解,图解旋转数组中的二分法
- [LeetCode] Sqrt(x)
- [LeetCode] Construct Binary Tree from Inorder and Postorder Traversal
- LeetCode题解——700.二叉树搜索树中的搜索
- LeetCode数据结构_C语言题解系列-链表
- leetcode 62. 不同路径-动态规划及优化,双100%
- LeetCode二叉树练习(二)
- 198、【动态规划】leetcode ——983. 最低票价:记忆化搜索(C++版本)
- 113、【树与二叉树】leetcode ——538. 把二叉搜索树转换为累加树:递增数组视角右中左遍历(C++版本)
- 112、【树与二叉树】leetcode ——108. 将有序数组转换为二叉搜索树:二分查找树(C++版本)
- 【leetcode】:109. 有序链表转换二叉搜索树
- 【leetcode】538/1038: 把二叉搜索树转化为累加树
- [LeetCode] 1305. All Elements in Two Binary Search Trees 两棵二叉搜索树中的所有元素
- [LeetCode] Magic Squares In Grid 网格中的神奇正方形
- [LeetCode] Prefix and Suffix Search 前后缀搜索
- [LeetCode] Trim a Binary Search Tree 修剪一棵二叉搜索树
- [LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树
- LeetCode Binary Search Summary 二分搜索法小结
- [LeetCode] 523. Continuous Subarray Sum 连续的子数组之和
- [LeetCode] 270. Closest Binary Search Tree Value 最近的二分搜索树的值
- [LeetCode] 240. Search a 2D Matrix II 搜索一个二维矩阵之二
- [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二
- [LeetCode] Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树
- LeetCode将有序数组转换为二叉搜索树
- 莫名其妙的越界错误原因之条件判断顺序——基于LeetCode 99题,恢复二叉搜索树
- leetcode算法235.二叉搜索树的最近公共祖先
- leetcode算法69.x 的平方根