LeetCode33：搜索旋转排序数组

曾经终败给现在 2024-04-06 12:43 72阅读 0赞

[链接][Link 1]  
![在这里插入图片描述][0f4d395c698d445aa730696f508e33c5.png]

### 思路：二分法 ###

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

1.  数组旋转后即分成左右两部分，都是**各自有序**的 ！
2.  二分法，分为两种情况：  
    如果`nums[mid]` 在**左**边，  
    ①再判断`target`是否也在左边，如果是则将 right 左移，  
    ②否则即`target`在右边，则将left 右移；
    
    如果`nums[mid]` 在**右**边，  
    ①再判断`target`是否也在右边，如果是则将 left 右移，  
    ②否则即`target`在左边，则将right 左移；

### Java实现： ###

class Solution {
        
        public int search(int[] nums, int target) {
        
            if(nums.length==0){
        
                return -1;
            }
            if(nums.length==1){
        
                return nums[0]==target? 0:-1;
            }
            int n=nums.length;
            int i=0;
            int j=n-1;
            while(i<=j){
        
                int mid=i+(j-i)/2;
                if(nums[mid]==target){
        
                    return mid;
                // 如果mid在左边, 注意nums[mid]可能等于nums[0]
                }else if(nums[0]<=nums[mid]){
        
                    // target也在左边
                    if(nums[0]<=target && target<nums[mid]){
        
                        j=mid-1;
                    }else{
        
                        i=mid+1;
                    }
                // 如果mid在右边
                }else if(nums[mid]<nums[0]){
        
                    // target也在右边
                    if(nums[mid]<target && target<=nums[n-1]){
        
                        i=mid+1;
                    }else{
        
                        j=mid-1;
                    }
                }
            }
            return -1;
        }
    }

[Link 1]: https://leetcode.cn/problems/search-in-rotated-sorted-array/
[0f4d395c698d445aa730696f508e33c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/b079374edea940ce9ff9ee1996c248d0.png
[941b35f44bc8452fa2601aee07d170bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/68cb4f502185450b9b93a4be82f04d76.png