LeetCode OJ：Search in Rotated Sorted Array（翻转排序数组的查找）
2024-09-01 11:27:14
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
相当于将数组的后面一部折叠到数组的前面去了，本质上也是二分法，这里其实也是有规律可循的：首先要得到转折点，也就是其左边右边都比其大的那一点。给一个start以及一个end，如果nums[mid] > nums[start]，那么说明从start到mid也一定是递增的，很容的知道pivot一定在mid+1到end之间，那么递归的去查找就可以了。nums[mid] < nums[start]可以同样的去分析，代码如下所示：
class Solution {
public:
int search(vector<int>& nums, int target) {
int pivot = getPivot(nums, , nums.size() - );
int pos = bSearch(nums, , pivot - , target);
if(pos != -)
return pos;
return bSearch(nums, pivot, nums.size() - , target);
}
int getPivot(vector<int>&nums, int start, int end){
if(start > end)
return -;
int mid = start + (end - start)/;
if(nums[start] <= nums[mid]){
int pos = getPivot(nums, mid + , end);
if(pos == -) return start;
else
if(nums[pos] < nums[start])
return pos;
else
return start;
}else{
int pos = getPivot(nums, start, mid);
if(pos == -)
return mid;
if(nums[pos] < nums[end])
return pos;
else
return mid;
}
}
int bSearch(vector<int>&nums, int start, int end, int target){
int mid;
while(start <= end){
mid = (start+end)/;
if(nums[mid] > target){
end = mid - ;
}else if(nums[mid] < target){
start = mid + ;
}else{
return mid;
}
}
return -; //返回-1，表明在这一部分没有找到，可以在下一部分查找
}
};
最新文章
- Android(Linux)实时监控串口数据
- 模拟apache commons dbutils 实现自己的BeanListHandler(回调应用)
- css中的1px并不总等于设备的1px（高分辨率不等 低分辨等）
- iOS中CocoaPads的安装与配置（总结）
- c1ctf2016 wp
- IOS中十六进制的颜色转换为UIColor
- 提高xshell使用效率
- Android App监听软键盘按键的三种方式（转）
- 蓝桥杯-逆波兰表达式-java
- Spring Boot 系列（四）静态资源处理
- Mysql 分区详解
- C++反汇编第六讲,认识C++中的Try catch语法,以及在反汇编中还原
- [NOIp 2009]靶形数独
- 大名鼎鼎的红黑树，你get了么？2-3树 绝对平衡 右旋转 左旋转 颜色反转
- react-native shadow失效
- NET Core 1.1中使用Jwt
- Visual Studio 2013 在使用 razor无智能提示的解决办法
- 项目部署相关命令（pm2）
- sas 数据集导出到excel
- oracle insert 返回ID