题目描述题解(二分查找)思路代码classSolution{publicintsearch(int[]nums,inttarget){if(numsnull||nums.length0){return-1;}intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;// 找到目标值直接返回下标if(nums[mid]target){returnmid;}// 判断左半部分是否有序if(nums[left]nums[mid]){// 判断 target 是否在有序的左半区间内if(targetnums[left]targetnums[mid]){rightmid-1;// target 在左半边缩小右边界}else{leftmid1;// target 在右半边缩小左边界}}// 否则右半部分一定是有序的else{// 判断 target 是否在有序的右半区间内if(targetnums[mid]targetnums[right]){leftmid1;// target 在右半边缩小左边界}else{rightmid-1;// target 在左半边缩小右边界}}}// 循环结束仍未找到返回 -1return-1;}}复杂度分析时间复杂度:O(logn)O(\log n)O(logn)其中nnn是数组 nums 的长度。整个算法核心就是一个标准的二分查找每次循环都会将搜索区间缩小一半空间复杂度:O(1)O(1)O(1)。我们只需要用到常数级别的几个指针变量 (left, right, mid)不需要额外的存储空间