题目: 搜索旋转排序数组 II

分析

方法一：暴力法

最朴素的方法是直接遍历整个数组，查找目标值。时间复杂度为 O(n)，其中 n 是数组的长度。

方法二：二分查找

由于数组部分有序，我们可以使用二分查找算法在数组中查找目标元素。由于数组中可能包含重复元素，因此在遇到 nums[mid] == nums[right] 时，我们无法确定 mid 的位置是左侧部分有序还是右侧部分有序。在这种情况下，我们只能将 right 减 1，逐渐缩小 right 的范围，直到该情况不再出现。此时，我们需要额外进行一次判断，若 nums[mid] == target，则说明找到了目标值。

时间复杂度：平均情况下为 O(log n)，在最坏情况下为 O(n)。

方法三：双指针法

由于数组中可能包含重复元素，因此在遇到 nums[i] == nums[j] 时，我们无法确定 i 和 j 之间的部分是否为有序数组。在这种情况下，我们只能将 i 加 1 并继续搜索。同时，我们注意到本题中数组中的元素都为整数，因此可以通过 nums[i] != nums[j] 的方式判断 i 和 j 之间是否存在其他元素。

时间复杂度：平均情况下为 O(n)，在最坏情况下为 O(n)。

下面是这三种方法的示例代码（使用 C++ 实现）：

方法一：暴力法