81. 搜索旋转排序数组 II

题目描述

有一个按非递减顺序排好的整数数组，其中可能有重复值。它在某个未知下标 k（0 <= k < nums.length）处被旋转：把前 k 个元素整体挪到末尾，得到 [nums[k], ..., nums[n-1], nums[0], ..., nums[k-1]]。例如 [0,1,2,4,4,4,5,6,6,7] 在下标 5 处旋转后成为 [4,5,6,6,7,0,1,2,4,4]。

输入旋转后的数组 nums 和整数 target。若 target 在数组中出现，返回 true，否则返回 false。

请尽量减少操作步数。

示例 1

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

解释：0 出现在下标 3 和 4。

示例 2

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

解释：数组中没有 3。

数据范围

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
保证 nums 是某个有序数组旋转后的结果。
-10^4 <= target <= 10^4

进阶：与不含重复元素的版本相比，重复值会不会影响时间复杂度？影响在哪里，原因是什么？

解题思路

每次取 mid，[lo, mid] 和 [mid, hi] 至少有一半是有序的。若 nums[lo] <= nums[mid]，左半有序，看 target 是否落在 [nums[lo], nums[mid]) 内决定往哪边走；否则右半有序，看 target 是否落在 (nums[mid], nums[hi]] 内。重复元素会造成 nums[lo] == nums[mid] == nums[hi]，此时分不清哪半有序，只能把两端各收缩一格。

为什么正确

若 target 在数组中，它一定在 [lo, hi] 内（被丢弃的部分要么确定不含 target，要么是与 nums[mid] 相等、且已确认不等于 target 的端点）。

复杂度分析

平均 O(log n)，大量重复时最坏 O(n)；空间 O(1)。

易错点

只用 nums[lo] <= nums[mid] 判断左半有序，在 [1,0,1,1,1] 这类输入上会出错，必须先处理三者相等的情况。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return True
            if nums[lo] == nums[mid] == nums[hi]:
                lo += 1
                hi -= 1
            elif nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return False

class Solution {
    public boolean search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
                lo++;
                hi--;
            } else if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return false;
    }
}

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
                lo++;
                hi--;
            } else if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return false;
    }
};

func search(nums []int, target int) bool {
	lo, hi := 0, len(nums)-1
	for lo <= hi {
		mid := (lo + hi) / 2
		if nums[mid] == target {
			return true
		}
		if nums[lo] == nums[mid] && nums[mid] == nums[hi] {
			lo++
			hi--
		} else if nums[lo] <= nums[mid] {
			if nums[lo] <= target && target < nums[mid] {
				hi = mid - 1
			} else {
				lo = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[hi] {
				lo = mid + 1
			} else {
				hi = mid - 1
			}
		}
	}
	return false
}

var search = function(nums, target) {
    let lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (nums[mid] === target) {
            return true;
        }
        if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) {
            lo++;
            hi--;
        } else if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return false;
};

function search(nums: number[], target: number): boolean {
    let lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (nums[mid] === target) {
            return true;
        }
        if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) {
            lo++;
            hi--;
        } else if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return false;
}

载入编辑器，自己跑一遍 →

二分查找专题的其他题目

查看二分查找全部题目 →