二分查找----5.寻找旋转排序数组中的最小值

题目链接

 

/**

        数组在某处进行旋转,分割为两个独立的递增区间,找出数组的最小值;特殊情况:若旋转次数是数组长度的倍数,则数组不变

        特点:

            常规情况:

                数组被分割为两个独立的子区间,左半区的最小值大于右半区的最大值

                依据数组长度,mid可能落在左半区也有可能落在右半区,最小值在右半区

            特殊情况:

                旋转次数是数组长度的倍数,则数组不变

                此时数组是一个完整的递增区间,取第一个元素即可

        二分策略:

            若left与right已经在一个递增区间中,则直接返回nums[left]即可;本身就是一个递增区间,或经过收缩left来到了右半区。

            若不在一个区间中,则判断mid所在半区;在左半区则淘汰[left,mid],在右半区则淘汰[mid,right]

            经过收缩后再重新判断left,right是否在同一区间,在则直接返回结果,不在则重复上述流程再次收缩

        判断条件:

            nums[left] <= nums[mid] && nums[mid] <= nums[right] ---> [left,right]已经在同一区间,直接返回结果即可

            仅满足:nums[left] <= nums[mid] ---> [left,right]不单调,且mid在左半区; 淘汰[left,mid]

            均不满足,[left,right]不单调,且mid在右半区; 淘汰[mid,right)

*/

class Solution {/**数组在某处进行旋转,分割为两个独立的递增区间,找出数组的最小值;特殊情况:若旋转次数是数组长度的倍数,则数组不变特点:常规情况:数组被分割为两个独立的子区间,左半区的最小值大于右半区的最大值依据数组长度,mid可能落在左半区也有可能落在右半区,最小值在右半区特殊情况:旋转次数是数组长度的倍数,则数组不变此时数组是一个完整的递增区间,取第一个元素即可二分策略:若left与right已经在一个递增区间中,则直接返回nums[left]即可;本身就是一个递增区间,或经过收缩left来到了右半区。若不在一个区间中,则判断mid所在半区;在左半区则淘汰[left,mid],在右半区则淘汰[mid,right]经过收缩后再重新判断left,right是否在同一区间,在则直接返回结果,不在则重复上述流程再次收缩判断条件:nums[left] <= nums[mid] && nums[mid] <= nums[right] ---> [left,right]已经在同一区间,直接返回结果即可仅满足:nums[left] <= nums[mid] ---> [left,right]不单调,且mid在左半区; 淘汰[left,mid]均不满足,[left,right]不单调,且mid在右半区; 淘汰[mid,right)*/public int findMin(int[] nums) {//双指针置于有效部分两端int left = 0, right = nums.length - 1;while(left <= right) {int mid = (left + right) >>> 1;//[left,right]已收缩至右半区直接返回结果即可if(nums[left] <= nums[mid] && nums[mid] <= nums[right]) {return nums[left];}//[left,right]不单调,且mid在左半区else if(nums[left] <= nums[mid]) { left = mid + 1; //淘汰[left,mid]}//[left,right]不单调,且mid在右半区else {right = mid; //淘汰[mid,right) ---> mid恰好为右半区第一个元素,避免错失最小值}}return -1;}
}