假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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
进阶:
- 这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
- 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么?
- 如何正确的二分
代码
class Solution {
public boolean search(int[] nums, int target) {
// 二分查找灵活运用
if (nums.length == 0) {
return false;
}
if (nums.length == 1) return nums[0] == target;
int l = 0;
int r = nums.length - 1;
// 目标值必然存在一个有序的子序列中
while(l <= r){
int mid = (l+r)/2;
if (nums[mid] == target){
return true;
}
if (nums[l] == nums[mid]){// 消除重复
l++;
continue;
}
if (nums[r] == nums[mid]){// 消除重复
r--;
continue;
}
if (nums[mid] < nums[r]) {
if(nums[mid] < target && nums[r] >= target){
l = mid + 1;
}else {
r = mid - 1;
}
}else {
if(nums[l] <= target && nums[mid] > target){
r = mid - 1;
}else {
l = mid + 1;
}
}
}
return false;
}
}
- 其他解法
- 从前顺序遍历或者从后顺序遍历
class Solution {
public boolean search(int[] nums, int target) {
boolean res=false;
int len=nums.length;
if(len==0)
return false;
int first=0;
int last=len-1;
if(nums[0]==target||nums[len-1]==target)
return true;
if(target>nums[first]){
while(first<len){
if(nums[first]<target){
first++;
}else if(nums[first]>target){
return false;
}else{
return true;
}
}
}
if(target<nums[last]){
while(last>=0){
if(nums[last]>target){
last--;
}else if(nums[last]<target){
return false;
}else{
return true;
}
}
}
return res;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
