面试随缘刷题--day3

leetcode no.33 搜索旋转排序数组

• 二分问题，注意边界和只有两个的考虑情况。

• 因为mid是起到向下取整的效果，因此要考虑好a[left]=a[mid]的情况

• 退出的条件为a[mid]==target或者l>r

• 对较大的部分的定义 4 5 6 7 1 2 3  此时4 5 6 7是较大的部分，判断mid所处单元用其与left处关系对比判断哦

• 大范围先判断mid和target的关系，进入分支以后确定mid是在较大还是正常部分

• a[mid]>target时，可能出现的情况：a[mid]在较大的那部分,那么说明前面都比a[mid]小，（此时若a[left]<=target），那么结果一定在[left,mid]中，注意带等号，不然就空掉了left处正好是target，反之，如果a[left]>target，那么结果一定在右半部分。而如果a[mid]在较小的部分，还是比target大，那么只有其左侧的部分才有可能。（7 1 2 3 4 5 6）这种序列

• a[mid]<target的时候，如果mid在较小的单元，那么可能在左侧的较大部分出现，也可能在右侧正常递增中出现，如果a[right]>=target，一定会出现在右侧。如果mid在较大单元，那么一定是在其右侧出现。

• 值得注意的是，因为每次在知道mid与target的关系后，都要先判断mid是在较大部分还是较小部分，而mid的产生是先根据(left right)/2产生的，那么他向下取整就有可能会触碰到a[left]==a[mid]的情况，因此，在判断较大较小时a[left]<=a[mid]是带等号的，右边就不需要（因为右边如果出现相等，那一定是left和right同，只有一个元素的）

class Solution {public:    int search(vector<int>& nums, int target) {        int len=nums.size();        int l,r,mid;        l=0;        r=len-1;        mid=(l r)/2;        while(l<=r)        {            //printf("%d %d\n",l,r);            if(nums[mid]==target)                return mid;            if(nums[mid]>target)            {                //printf("hah1");                if(nums[l]<=nums[mid])//4 5 6 7 1 2 3                {                    //printf("hah2");                    if(nums[l]<=target)                        r=mid-1;                    else                        l=mid 1;                }                else                    r=mid-1;            }            else//nums[mid]<target            {                if(nums[l]<nums[mid])                    l=mid 1;                else                {                    if(nums[r]>=target)                    {                        l=mid 1;                    }                    else                        r=mid-1;                }            }            mid=(l r)/2;        }        return -1;    }};

View Code来源：https://www.icode9.com/content-4-725201.html