81.搜索旋转排序数组II

本文主要是介绍81.搜索旋转排序数组II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

81.搜索旋转排序数组II

解题思路：

package leadcode;/*** @author : icehill* @description : 搜索旋转排序数组II* 已知存在一个按非降序排列的整数数组 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* -10^4 <= nums[i] <= 10^4* 题目数据保证 nums 在预先未知的某个下标上进行了旋转* -10^4 <= target <= 10^4* 进阶：* 这是 搜索旋转排序数组的延伸题目，本题中的nums 可能包含重复元素。* 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？* 来源：力扣（LeetCode）* 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。* 解题思路：* 即使数组被旋转过，我们仍然可以利用这个数组的递增性，使用二分查找。对于当前的中点，* 如果它指向的值小于等于右端，那么说明右区间是排好序的；反之，那么说明左区间是排好序的。* 如果目标值位于排好序的区间内，我们可以对这个区间继续二分查找；反之，我们对于另一半区* 间继续二分查找。* 注意，因为数组存在重复数字，如果中点和左端的数字相同，我们并不能确定是左区间全部* 相同，还是右区间完全相同。在这种情况下，我们可以简单地将左端点右移一位，然后继续进行二分查找。* @date : 2021-05-19*/
public class Solution81 {public static void main(String[] args) {int[] nums = {1, 0, 1, 1, 1};Solution81 solution81 = new Solution81();System.out.println(solution81.search(nums, 3));System.out.println(solution81.search(nums, 0));}public boolean search(int[] nums, int target) {int left = 0;int right = nums.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[right]) {left = mid + 1;} else {right = mid - 1;}}}return false;}
}