33.搜索旋转排序数组

题目描述

题解(二分查找)

思路

代码

classSolution{publicintsearch(int[]nums,inttarget){if(nums==null||nums.length==0){return-1;}intleft=0;intright=nums.length-1;while(left<=right){intmid=left+(right-left)/2;// 找到目标值，直接返回下标if(nums[mid]==target){returnmid;}// 判断左半部分是否有序if(nums[left]<=nums[mid]){// 判断 target 是否在有序的左半区间内if(target>=nums[left]&&target<nums[mid]){right=mid-1;// target 在左半边，缩小右边界}else{left=mid+1;// target 在右半边，缩小左边界}}// 否则右半部分一定是有序的else{// 判断 target 是否在有序的右半区间内if(target>nums[mid]&&target<=nums[right]){left=mid+1;// target 在右半边，缩小左边界}else{right=mid-1;// target 在左半边，缩小右边界}}}// 循环结束仍未找到，返回 -1return-1;}}

复杂度分析

• 时间复杂度:O(log⁡n)O(\log n)O(logn)，其中nnn是数组 nums 的长度。整个算法核心就是一个标准的二分查找，每次循环都会将搜索区间缩小一半
• 空间复杂度:O(1)O(1)O(1)。我们只需要用到常数级别的几个指针变量 (left, right, mid)，不需要额外的存储空间