leetcode 33. 搜索旋转排序数组【二分查找：利用有序的一边缩小范围】

客官°小女子只卖身不卖艺 2022-11-16 13:57 119阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

> 我们还是想向之前那样查找，因为只翻折了一次  
> 所以如图，左侧的最低点肯定比右侧的最高点高（数组没有重复元素）  
> 如果a\[l\] < a\[m\]，那么\[l,m\]就是有序的  
> 如果啊a\[m\] < a\[r\] 那么\[m,r\]就是有序的  
> 每次缩小完二分的区间 取一个mid，总有一半是有序的，  
> 这样就可以判断taget在不在有序的区间里面，从而缩小一半空间

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

![在这里插入图片描述][20210407144501697.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221022/0d389a37161e4e6e820d77033c3fd48b.png
[20210407144501697.png]: /images/20221022/a67de3dc2c7047de81c85ed7aad9064c.png