LeetCode 每日一题笔记 日期：2026.05.22 题目：33. 搜索旋转排序数组

LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.22
• 题目：33. 搜索旋转排序数组
• 难度：中等
• 标签：数组、二分查找

1. 题目理解

问题描述：
给定一个升序数组，在未知下标k处左旋后，得到数组nums（所有值互不相同）。给定目标值target，返回它在数组中的下标，不存在则返回-1。要求时间复杂度为O(log⁡n)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与有序区间的边界关系，决定下一步的搜索方向。

算法步骤

1. 初始化左右指针left = 0，right = nums.length - 1；
2. 循环直到left > right：
   • 计算mid = left + (right - left) / 2；
   • 若nums[mid] == target，直接返回mid；
   • 判断左半区是否有序（nums[mid] >= nums[left]）：
     • 若target在左半区范围内，收缩右边界；
     • 否则收缩左边界；
   • 若右半区有序：
     • 若target在右半区范围内，收缩左边界；
     • 否则收缩右边界；
3. 循环结束未找到，返回-1。

3. 代码实现

packagelc33;publicclassSolution{publicintsearch(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]==target){returnmid;}// 左半区有序if(nums[mid]>=nums[left]){if(target>=nums[left]&&target<nums[mid]){right=mid-1;}else{left=mid+1;}}// 右半区有序else{if(target>nums[mid]&&target<=nums[right]){left=mid+1;}else{right=mid-1;}}}return-1;}}

4. 代码优化说明

减少冗余判断，通过逻辑等价简化分支，保持可读性的同时压缩代码：

packagelc33;publicclassSolution{publicintsearch(int[]nums,inttarget){intleft=0,right=nums.length-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]==target)returnmid;if(nums[mid]>=nums[left]){left=(target>=nums[left]&&target<nums[mid])?left:mid+1;right=(target>=nums[left]&&target<nums[mid])?mid-1:right;}else{left=(target>nums[mid]&&target<=nums[right])?mid+1:left;right=(target>nums[mid]&&target<=nums[right])?right:mid-1;}}return-1;}}

5. 复杂度分析

• 时间复杂度：O(log⁡n)O(\log n)O(logn)
  二分查找每次将区间减半，最坏情况下执行log⁡2n\log_2 nlog2​n次循环。

• 空间复杂度：O(1)O(1)O(1)
  仅使用常数级额外变量，无递归栈或额外数组开销。

6. 总结

• 核心思路：局部有序的二分查找，利用旋转数组的特性，每次只在有序区间内判断目标值位置；
• 关键技巧：通过nums[mid]与nums[left]的大小关系，快速判断哪一侧区间有序；
• 优化后代码通过三目运算符简化分支，逻辑更紧凑，同时保持原算法的正确性与时间复杂度。