hot100-53搜索旋转排序数组

一、题目

nums升序排列，值互不相同，经过k次旋转，找出target的下标，如果没有返回-1。

二、思路

每次比较nums[mid]与nums[left]和nums[right]，判断mid在哪一段，再决定如何缩小范围。

1. 如果nums[left] <= nums[mid]：

→ 左半段[left, mid]是升序的

• 若target在这个范围内（即left <= target <= mid），则在左半段找

• 否则，在右半段找

2. 如果nums[left] > nums[mid]：

→ 右半段[mid, right]是升序的

• 若target在这个范围内（即mid <= target <= right），则在右半段找

• 否则，在左半段找

总结：利用旋转数组“两段有序”的特性，通过比较nums[mid]与nums[left]和nums[right]判断哪一半是有序的，然后根据target是否落在该有序段内来决定搜索方向，实现高效的二分查找。

三、代码

class Solution { public int search(int[] nums, int target) { int left = 0, right = nums.length-1; while(left <= right){ int mid = left + (right - left) /2; if(target == nums[mid]) return mid; if(nums[left] < nums[mid]){ 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; } }

总结：通过判断哪一段有序，再看 target 是否在该段的值域内，决定搜索方向。