建设银行锦州分行网站,今网科技,wordpress 更好 知乎,杭州做网站的科技公司文章目录题目描述思路 代码更新版题目描述
值互不相同#xff1a;不用考虑重复值情况#xff08;要不然比较麻烦#xff09;
思路 代码
重点在于保证O(logn)的时间复杂度看成两个数组#xff1a;前半段 后半段。根据两个数组的极值来判断 target 在哪…
文章目录题目描述思路 代码更新版题目描述
值互不相同不用考虑重复值情况要不然比较麻烦
思路 代码
重点在于保证O(logn)的时间复杂度看成两个数组前半段 后半段。根据两个数组的极值来判断 target 在哪个数组再进行判断即可。先一次二分找到前半段、后半段的分界下标。再一次二分找到在某半段中的 target注意要考虑极端情况在下标0处旋转相当于没有旋转。
class Solution {public int search(int[] nums, int target) {// 思路一次分割点查找O(logn)。两次二分查找O(logn)int k -1, low 0, top nums.length - 1;while(low top){k (low top) / 2;// 找到的情况注意长度为1时需要进行k 1 nums.length判断if(k 1 nums.length || nums[k] nums[k 1]){break;}if(nums[k] nums[0]){top k - 1;}else{low k 1;} }// 判断选择在哪个部分进行二分if(target nums[nums.length-1] || k nums.length-1){return binary(nums,0,k,target);}else{return binary(nums,k1,nums.length-1,target);}}public int binary(int[] nums,int left,int right,int target){// l 0r -1的情况也要考虑if(left right){if(target nums[left]){return left;}return -1;}int half (leftright)/2;// 相等判断if(target nums[half]){return half;}// 缩短范围-1去掉已判断的halfelse if(target nums[half]){return binary(nums,half1,right,target);}else{return binary(nums,left,half-1,target);}}
}更新版
核心在于两次二分以及对数组性质的使用
class Solution {public int search(int[] nums, int target) {int k -1;int left 0, right nums.length - 1;while(left right) {k (left right) / 2;if(k 1 nums.length || nums[k] nums[k 1]) {break;}if(nums[k] nums[0]) {right k - 1;}else {left k 1;}}if(target nums[nums.length - 1] || k nums.length - 1) {return binary(nums, 0, k, target);}else {return binary(nums, k 1, nums.length - 1, target);}}public int binary(int[] nums, int left, int right, int target) {if(left right) {return -1;}int mid (left right) / 2;if(target nums[mid]) {return mid;}else if(nums[mid] target) {return binary(nums, left, mid - 1, target);}else {return binary(nums, mid 1, right, target);}}
}
