自己做网站可以上传软件下载,怎样了解网站建设是否专业,网络科技公司 网站建设,南阳微信网站leetCode33. 搜索旋转排序数组 题目思路
此题的特点是#xff1a;排好序循环的数组#xff1a;特点#xff1a;可以分为两个区间#xff0c;一半升序#xff0c;一半降序#xff0c;或者全部升序
我们可以用二分法#xff0c;找出升序 到降序的那个临界值#xff0c;并…leetCode33. 搜索旋转排序数组 题目思路
此题的特点是排好序循环的数组特点可以分为两个区间一半升序一半降序或者全部升序
我们可以用二分法找出升序 到降序的那个临界值并记录号那个临界值
然后在用target 跟nums[0]进行比较因为他是升序的首元素升序部分它最小从而判断往左区间走还是往右区间走
更新新的区间后
在用二分法找到这个target
力扣特色必须判断数组为空的情况代码
class Solution {
public:int search(vectorint nums, int target) {if(nums.empty()) return -1;int left 0, right nums.size() - 1;// 第一个二分找出区间临界点(升区间的临界点) 区间是找出升序的区间while(left right){ // 模板一int mid left right 1 1;if(nums[mid] nums[0]) left mid;else right mid - 1;} // left right// 找target是往左右那个升区间走if(target nums[0]) left 0;else {left right 1;right nums.size() - 1;}// 第二次二分找出那个target的下标while(left right){ // 模板二int mid left (right - left 1);if(nums[mid] target) right mid;else left mid 1;} // left rightif(nums[right] target) return right; // 返回的一定使用right进行比较的因为left的值会大于right,用left的话说不定会越界else return -1;}
};
