LeetCode.81 搜索旋转排序数组Java

爱被打了一巴掌 2024-04-19 08:21 71阅读 0赞

# LeetCode.81 搜索旋转排序数组 #

![\[外链图片转存失败(img-EFAiXMMG-1568551702709)(media/15685515904124/15685516078211.jpg)\]][img-EFAiXMMG-1568551702709_media_15685515904124_15685516078211.jpg]

注意：

1.  通过mid和左边数字大小可以判断到底是左边有序还是右边有序
2.  需要处理重复数字最后才能通过？？？

代码：

class Solution { 
        public boolean search(int[] nums, int target) { 
                if (nums.length == 0) { 
                    return false;
                }
                int start = 0, end = nums.length - 1;
                while (start <= end) { 
                    // 处理重复数字
                    while (start < end && nums[start] == nums[start + 1]) { 
                        start++;
                    }
                    while (start < end && nums[end] == nums[end - 1]) { 
                        end--;
                    }
                    int mid = (start + end) / 2;
                    if (nums[mid] == target) { 
                        return true;
                    }
                    if (nums[mid] >= nums[start]) { 
                        // 左边有序{4,5,6,1,2,3}
                        if (target < nums[mid] && target >= nums[start]) { 
                            end = mid - 1;
                        } else { 
                            start = mid + 1;
                        }
                    } else { 
                        // 右边有序
                        if (target > nums[mid] && target <= nums[end]) { 
                            start = mid + 1;
                        } else { 
                            end = mid - 1;
                        }
                    }
                }
                return false;
            }
    
    }

[img-EFAiXMMG-1568551702709_media_15685515904124_15685516078211.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2a603a367cb647d0bc401d5e3cb6a6ba.png