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