简单二分查找：搜索旋转排序数组

傷城~ 2023-10-06 16:51 57阅读 0赞

## 简单二分查找：搜索旋转排序数组 ##

#### 问题： ####

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

#### 思路：二分查找（ 时间：O（log n）） ####

二分查找只能用于有序序列，旋转后的序列不是有序序列，但是用二分查找中的mid将数组一分为二后，总有一半的数组是有序的 （可用反证法证明）。可以在这部分有序数组中使用二分查找

#### 代码： ####

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210316103803923.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021031610382226.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70