企业官网建设流程全解析

LeetCode 153 题「寻找旋转排序数组中的最小值」要求以 O(log n) 的时间复杂度找出旋转后的升序数组中的最小元素。由于数组无重复元素，可以使用二分查找。

Java 实现

classSolution{publicintfindMin(int[]nums){intleft=0;intright=nums.length-1;while(left<right){intmid=left+(right-left)/2;// 如果中间元素大于右边界元素，说明最小值在 mid 的右侧if(nums[mid]>nums[right]){left=mid+1;}else{// 否则最小值在 mid 的左侧或就是 midright=mid;}}// 循环结束时 left == right，指向最小值returnnums[left];}}

思路解析

· 旋转后的数组可以看作两个升序段，最小值是第二段的第一个元素。
· 比较 nums[mid] 与 nums[right]：
· 若 nums[mid] > nums[right]，说明 mid 在第一段（较大值区域），最小值一定在 mid 右侧，因此 left = mid + 1。
· 否则 mid 在第二段（较小值区域），最小值可能在 mid 或 mid 左侧，因此 right = mid。
· 每次循环缩小一半范围，最终 left 和 right 相遇，即为最小值。

时间复杂度：O(log n)，空间复杂度：O(1)。