【LeetCode 33】搜索旋转排序数组
2023-09-14 09:03:43 时间
【题解】
会发现旋转之后,假设旋转点是i 则0..i-1是递增有序的。然后i..len-1也是递增有序的。 且nums[i..len-1]【代码】
class Solution {
public:
int search(vector<int>& nums, int target) {
int l,r;
l = 0;r = ((int)nums.size()) - 1;
while (l<=r){
int mid = (l+r)/2;
if (nums[mid]>=nums[0]){
//取的中间点在左边这一段。
if (target>=nums[0]){
//目标也在左边这一段,那就根据和它的大小比.
if(target<nums[mid]){
r = mid-1;
}else{
l = mid+1;
}
}else{
//目标不在左边这一段(即在右边那一段)
l = mid + 1;
}
}else{
//取的中间点在右边这一段
if (target>=nums[0]){
//目标在左边那一段
r = mid-1;
}else{//在右边那一段
if (target<nums[mid]){
r = mid-1;
}else{
l = mid+1;
}
}
}
}
if (l-1>=0 && target==nums[l-1]){
return l-1;
}else return -1;
}
};
相关文章
- Leetcode 之Length of Last Word(37)
- Java实现 LeetCode 712 两个字符串的最小ASCII删除和(最长公共子串&&ASCII值最小)...
- Java实现 LeetCode 688 “马”在棋盘上的概率(DFS+记忆化搜索)
- Java实现 LeetCode 581 最短无序连续子数组(从两遍搜索找两个指针)
- Java实现 LeetCode 450 删除二叉搜索树中的节点
- Java实现 LeetCode 230 二叉搜索树中第K小的元素
- Java实现 LeetCode 108 将有序数组转换为二叉搜索树
- Java实现 LeetCode 26 删除排序数组中的重复项
- LeetCode(108):将有序数组转换为二叉搜索树
- LeetCode(33):搜索旋转排序数组
- LeetCode(87):扰乱字符串
- ( “树” 之 BST) 669. 修剪二叉搜索树 ——【Leetcode每日一题】
- 【LeetCode Python实现】33. 搜索旋转排序数组(中等)
- 【LeetCode 简单 数组】35 搜索插入位置
- Leetcode 1588. 所有奇数长度子数组的和
- leetcode 599. Minimum Index Sum of Two Lists
- 【LeetCode】79. 单词搜索
- leetcode 搜索旋转排序数组