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

Categories:

题目描述
思路分析
1. 解法一：二分查找 + 去重（推荐）
相似题目

题目描述

✅ 81. 搜索旋转排序数组 II

思路分析

解法一：二分查找 + 去重（推荐）

核心思路：

数组为旋转排序但允许重复，无法确定有序段时收缩边界。

每次比较 mid 与 right，判断哪一侧有序并缩小搜索区间。

若 nums[mid] == nums[right]，右边界左移以去重。

复杂度分析：

时间复杂度：O(n) 最坏，平均接近 O(log n)。

空间复杂度：O(1)。

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }

            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid] > nums[right]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                right--;
            }
        }

        return false;
    }
}

func search(nums []int, target int) bool {
	left, right := 0, len(nums)-1

	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return true
		}

		if nums[mid] < nums[right] {
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		} else if nums[mid] > nums[right] {
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			right--
		}
	}

	return false
}

相似题目

题目	难度	考察点
33. 搜索旋转排序数组	中等	二分查找
153. 寻找旋转排序数组中的最小值	中等	二分查找
154. 寻找旋转排序数组中的最小值 II	困难	二分查找
704. 二分查找	简单	二分模板
81. 搜索旋转排序数组 II	中等	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/05902279