题目列表

• 162 Find Peak Element
• 153 Find Minimum in Rotated Sorted Array
• 154 Find Minimum in Rotated Sorted Array II
• 33 Search in Rotated Sorted Array
• 81 Search in Rotated Sorted Array II

162. Find Peak Element

题解

二分  
对于l, r, mid
分析三个点mid, mid-1, mid+1  
1.nums[ mid ] > nums[ mid - 1 ] && nums[ mid ] > nums[ mid + 1 ]
//mid即为Peak Element
2.nums[ mid ] > nums[ mid - 1 ] && nums[ mid ] < nums[ mid + 1 ]
//Peak Element一定存在于[ mid + 1, r ]区间
3.nums[ mid ] < nums[ mid - 1 ] && nums[ mid ] > nums[ mid + 1 ]
//Peak Element一定存在于[ l, mid - 1 ]区间
4.nums[ mid ] < nums[ mid - 1 ] && nums[ mid ] < nums[ mid + 1 ]
//Peak Element一定存在于[ l, mid - 1 ]或[ mid + 1, r ]区间,任取一个即可

注意mid为0或n-1的情况

代码

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        if( n == 1 ) return 0;
        while( l <= r  )
        {
            int m = l + r >> 1;
            if( m == 0 && nums[ m ] > nums[ m + 1 ] ) return m;
            if( m == n - 1 && nums[ m ] > nums[ m - 1 ] ) return m;
            if( nums[ m ] > nums[ m - 1 ] && nums[ m ] > nums[ m + 1 ] ) return m;
            if( nums[ m ] < nums[ m + 1 ] ) l = m + 1;
            else                            r = m - 1;
        }
    }
};

153. Find Minimum in Rotated Sorted Array

题解

二分
分析三个点l, mid, r
1.nums[ mid ] < nums[ r ]
//从mid~r处都为递增,最小点在l~mid处, r = mid
2.nums[ mid ] > nums[ r ]
//表明maxnum与minnum的分界点在mid + 1~r处,即最小值在mid + 1 ~ r处, l = mid + 1

代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while( l < r )
        {
            int mid = l + r >> 1;
            if( nums[ mid ] < nums[ r ] ) r = mid;
            else                          l = mid + 1;
        }
        return nums[ r ];
    }
};

154. Find Minimum in Rotated Sorted Array II

题解

二分
分析三个点l, mid, r
1.nums[ mid ] < nums[ r ]
//从mid~r处都为递增,最小点在l~mid处, r = mid
2.nums[ mid ] == nums[ r ]
// 分为两种情况 2 2 2 1 2     2 3 2 2 2 
// 说明 l ~ mid 或 mid ~ r 两者之间一定有一个区间都是同一个值
// 检测mid~r区间
// 若为同一个值,那么最小值在l~mid区间 r = mid
// 若不为同一个值,记不同值的那个点为i, 那么最小值在 i ~ r区间 l = i
3.nums[ mid ] > nums[ r ]
// 表明maxnum与minnum的分界点在mid + 1~r处,即最小值在mid + 1 ~ r处, l = mid + 1

代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while( l < r )
        {
            int mid = l + r >> 1;
            if( nums[ mid ] < nums[ r ] ) r = mid;
            else if( nums[ mid ] == nums[ r ] )
            {
                int flag = -1;
                for( int i = mid + 1; i <= r; ++ i )
                {
                    if( nums[ i ] != nums[ mid ] )
                    {
                        flag = i;
                        break;
                    }
                }
                if( flag == -1 ) r = mid;
                else             l = flag;
            }
            else l = mid + 1;
        }
        return nums[ r ];
    }
};

153与154总结

注意while( l < r )这个条件
在153中,可以写成 while( l <= r )
分析下当l == r 时, l == mid, mid == r, 此时 l = mid + 1,会退出循环
在154中, 不能写成 while( l <= r )
分析下当l == r 时, l == mid, mid == r, 此时 r = mid, 会产生无限循环
所以说二分的写法不是固定的,根据题目的要求,具体写法也不同.

33. Search in Rotated Sorted Array

题解

二分
分析三个点l, mid, r 和target的值
1. nums[ mid ] == target 
// 找到target值,返回mid
2. nums[ mid ] < target
// 需要找到比nums[ mid ]大的那个区间
// 1.当nums[ mid ] > nums[ l ]时,
//   表明 l ~ mid这个区间是递增的,都比target小, l = mid + 1
// 2.当nums[ mid ] < nums[ l ]时
//   表明maxnum与minnum的分界点在l~mid中,所以mid~r这个区间是递增的,
//   当target>nums[ r ]时,表明mid~r这个区间的值都比target小, 在l~mid - 1区间中
//   否则在mid + 1~r区间中
3. nums[ mid ] > target
// 需要找到比nums[mid]小的那个区间
// 1. 当nums[ mid ] < nums[ r ]时
//    表明mid~r这个区间是递增的,都比target大, r = mid - 1
// 2. 当nums[ mid ] > nums[ r ]时
//    表明maxnum与minnum的分界点在mid~r中,所以l~mid这个区间是递增的,
//    当target < nums[ l ]时,表明l~mid这个区间的值都比target大,在mid+1~r区间中
//    否则在l~mid-1区间中

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while( l <= r )
        {
            int mid = l + r >> 1;
            if( nums[ mid ] == target )  return mid;
            else if( nums[ mid ] < target )
            {
                if( nums[ mid ] > nums[ l ] ) l = mid + 1;
                else if( target > nums[ r ] ) r = mid - 1;
                else l = mid + 1;
            }
            else
            {
                if( nums[ mid ] < nums[ r ] ) r = mid - 1;
                else if( target < nums[ l ] ) l = mid + 1;
                else r = mid - 1;
            }
        }
        return -1;
    }
};

81. Search in Rotated Sorted Array II

题解

//这个题的逻辑跟33. Search in Rotated Sorted Array基本一模一样
//只是需要额外添加一种情况  2 2 2 1 2     2 3 2 2 2 
//如同154. Find Minimum in Rotated Sorted Array II
//为了方便
//每次当求出mid后,求出与nums[ mid ]值相同的区间[ a + 1, b - 1 ];
int a = mid, b = mid;
while( nums[ mid ] == nums[ a ] && a >= l )  -- a;
while( nums[ mid ] == nums[ b ] && b <= r )  ++ b;
//当 a = l - 1 且 b = r + 1时,表明不存在
//当 a = l - 1时,表明 l ~ mid 相同,则 l = b
//当 b = r + 1时,表示 mid ~ r 相同,则 r = a
//剩下的情况和33. Search in Rotated Sorted Array基本一样

代码

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while( l <= r  )
        {
            int mid = l + r >> 1;
            if( nums[ mid ] == target ) return true;
            int a = mid, b = mid;
            while( nums[ mid ] == nums[ a ] && a >= l ) -- a;
            while( nums[ mid ] == nums[ b ] && b <= r )  ++ b;
            if( a == l - 1 && b == r + 1 ) return false;
            if( a == l - 1 )
            {
                l = b;
                continue;
            }
            if( b == r + 1 )
            {
                r = a;
                continue;
            }
            if( nums[ mid ] < target )
            {
                if( nums[ mid ] > nums[ l ] ) l = b;
                else if( target > nums[ r ] ) r = a;
                else l = b;
            }
            else
            {
                if( nums[ mid ] < nums[ r ] ) r = a;
                else if( target < nums[ l ] ) l = b;
                else r = a;
            }
        }
        return false;
    }
};