LeetCode 每日一题笔记0. 前言日期2026.05.22题目33. 搜索旋转排序数组难度中等标签数组、二分查找1. 题目理解问题描述给定一个升序数组在未知下标k处左旋后得到数组nums所有值互不相同。给定目标值target返回它在数组中的下标不存在则返回-1。要求时间复杂度为O(logn)O(\log n)O(logn)。示例输入nums [4,5,6,7,0,1,2],target 0输出4解释目标值0位于下标4。输入nums [4,5,6,7,0,1,2],target 3输出-1解释目标值不存在于数组中。2. 解题思路核心观察旋转后的数组仍保持局部有序被mid分成的两个区间中必有一个是完全有序的利用二分查找先判断mid所在的区间是否有序再根据target与有序区间的边界关系决定下一步的搜索方向。算法步骤初始化左右指针left 0right nums.length - 1循环直到left right计算mid left (right - left) / 2若nums[mid] target直接返回mid判断左半区是否有序nums[mid] nums[left]若target在左半区范围内收缩右边界否则收缩左边界若右半区有序若target在右半区范围内收缩左边界否则收缩右边界循环结束未找到返回-1。3. 代码实现packagelc33;publicclassSolution{publicintsearch(int[]nums,inttarget){intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}// 左半区有序if(nums[mid]nums[left]){if(targetnums[left]targetnums[mid]){rightmid-1;}else{leftmid1;}}// 右半区有序else{if(targetnums[mid]targetnums[right]){leftmid1;}else{rightmid-1;}}}return-1;}}4. 代码优化说明减少冗余判断通过逻辑等价简化分支保持可读性的同时压缩代码packagelc33;publicclassSolution{publicintsearch(int[]nums,inttarget){intleft0,rightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target)returnmid;if(nums[mid]nums[left]){left(targetnums[left]targetnums[mid])?left:mid1;right(targetnums[left]targetnums[mid])?mid-1:right;}else{left(targetnums[mid]targetnums[right])?mid1:left;right(targetnums[mid]targetnums[right])?right:mid-1;}}return-1;}}5. 复杂度分析时间复杂度O(logn)O(\log n)O(logn)二分查找每次将区间减半最坏情况下执行log2n\log_2 nlog2n次循环。空间复杂度O(1)O(1)O(1)仅使用常数级额外变量无递归栈或额外数组开销。6. 总结核心思路局部有序的二分查找利用旋转数组的特性每次只在有序区间内判断目标值位置关键技巧通过nums[mid]与nums[left]的大小关系快速判断哪一侧区间有序优化后代码通过三目运算符简化分支逻辑更紧凑同时保持原算法的正确性与时间复杂度。
