php做网站的好处,厦门做网站需要多少钱,wordpress get_search_form(),百度指数手机版2023.9.26 本题暴力法可以直接A#xff0c;但是题目要求用log n的解法。 可以想到二分法#xff0c;但是一般二分法适用于有序数组的#xff0c;这里的数组只是部分有序#xff0c;还能用二分法吗#xff1f; 答案是可以的。因为数组是经过有序数组旋转得来的#xff0c;…2023.9.26 本题暴力法可以直接A但是题目要求用log n的解法。 可以想到二分法但是一般二分法适用于有序数组的这里的数组只是部分有序还能用二分法吗 答案是可以的。因为数组是经过有序数组旋转得来的所以在二分之后左右两边必有一边是有序的。 具体细节看代码
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size()-1;while(left right){int mid (left right) / 2;if(nums[mid] target) return mid;//左半边升序的情况if(nums[0] nums[mid]){if(target nums[mid] target nums[0]){right mid - 1;}else left mid 1;}//右半边升序的情况else{if(target nums[mid] target nums[nums.size()-1]){left mid 1;}else right mid - 1;}}return -1;}
};
