LeetCode_二分搜索_中等_81.搜索旋转排序数组 II

逃离我推掉我的手 2023-10-06 19:09 42阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

已知存在一个按非降序排列的整数数组 nums ，**数组中的值不必互不相同**。  
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转 ，使数组变为 \[nums\[k\], nums\[k+1\], …, nums\[n-1\], nums\[0\], nums\[1\], …, nums\[k-1\]\]（下标 从 0 开始 计数）。例如， \[0,1,2,4,4,4,5,6,6,7\] 在下标 5 处经旋转后可能变为 \[4,5,6,6,7,0,1,2,4,4\] 。  
给你旋转后的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

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

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

**提示：**  
1 <= nums.length <= 5000  
\-104 <= nums\[i\] <= 104  
题目数据保证 nums 在预先未知的某个下标上进行了旋转  
\-104 <= target <= 104

**进阶：**  
这是33.搜索旋转排序数组的延伸题目，本题中的 nums 可能包含重复元素。  
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

## 2.思路 ##

（1）二分搜索  
本题与[33.搜索旋转排序数组][33.]这题类似，只不过本题中数组中的值不必互不相同，即数组中可能有重复元素，那么在使用二分搜索时就可能会出现 **nums\[left\] = nums\[mid\] = nums\[right\]** 的情况，此时不能判断区间 \[left, mid\] 和区间 \[mid, right\] 的有序性。所以针对这种情况，只能将当前的二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找即可。

（2）顺序查找法  
如果不考虑时间复杂度，也可以考虑使用最简单的顺序查找法。

相关题目：  
[LeetCode\_二分搜索\_中等\_33.搜索旋转排序数组][33.]  
[LeetCode\_二分搜索\_中等\_153.寻找旋转排序数组中的最小值][LeetCode_153.]  
[LeetCode\_二分搜索\_困难\_154.寻找旋转排序数组中的最小值 II][LeetCode_154._ II]

## 3.代码实现（Java） ##

//思路1————二分搜索
    class Solution {
        
    	public boolean search(int[] nums, int target) {
        
    	    int length = nums.length;
    	    int left = 0, right = length - 1;
    	    while (left <= right) {
        
    	        int mid = (left + right) / 2;
    	        if (nums[mid] == target) {
        
    	            return true;
    	        }
    	        if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
        
    	            //消除数组中重复元素给二分查找带来的影响
    	            left++;
    	            right--;
    	        } else if (nums[left] <= nums[mid]) {
        
    	            if (nums[left] <= target && target < nums[mid]) {
        
    	                right = mid - 1;
    	            } else {
        
    	                left = mid + 1;
    	            }
    	        } else {
        
    	            if (nums[mid] < target && target <= nums[length - 1]) {
        
    	                left = mid + 1;
    	            } else {
        
    	                right = mid - 1;
    	            }
    	        }
    	    }
    	    return false;
    	}
    }

//思路2————顺序查找法
    class Solution {
        
    	public boolean search(int[] nums, int target) {
        
    	    for (int i = 0; i < nums.length; i++) {
        
    	        if (target == nums[i]) {
        
    	            return true;
    	        }
    	    }
    	    return false;
    	}
    }

[33.]: https://blog.csdn.net/weixin_43004044/article/details/118211776
[LeetCode_153.]: https://leetcode.cn/problems/search-in-rotated-sorted-array/
[LeetCode_154._ II]: https://blog.csdn.net/weixin_43004044/article/details/129377572