给定一个非降序的数组 
，对第 
位之后的部分进行旋转（将 
及以后的部分按原数组顺序移到前面），即 中的元素满足 
。
例如，对于数组 
，取 
进行旋转，那么得到的数组是 
特殊的 ， 若 
，则原数组不发生任何改变。
现在给定一个数 
，请你在数组 中搜索 是否存在。若存在则返回 true ，否则返回 false 。
要求空间复杂度 %5C)
，时间复杂度 %5C)
[编程题]旋转排序数组搜索 ii
/** 旋转数组中寻找target，主要考虑左、右边界与中间元素相等
3 1 2 3 3 3 3
3 3 3 3 1 2 3 这种情况无法排除掉保留那一半数据，只能去掉首尾元素缩进，退化到O(n)复杂度
**/
class Solution {
public:
bool search(int A[], int n, int target)
{
int low = 0,high = n-1;
while(low<=high)
{
int middle = (low+high)>>1;
if(A[middle] == target)
return true;
if(A[middle]==A[high] && A[middle]==A[low]) /// 比unique查找多了两句
{
low++;
high--;
}
else if(A[low] <= A[middle]) /// left side is sorted
{
if(A[low]<=target && target<A[middle])
high = middle-1;
else
low = middle+1;
}
else /// right side id sorted
{
if(A[middle]<target && target<=A[high])
low = middle+1;
else
high = middle-1;
}
}
return false;
}
};
编辑于 2017-07-13 21:37:51
回复(0)
import java.util.*;
public class Solution {
public boolean search(int[] A, int target) {
Arrays.sort(A);
int low = 0;
int high = A.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if(A[mid] == target) return true;
else if(A[mid] > target) high = mid - 1;
else low = mid + 1;
}
return false;
}
}
编辑于 2017-03-24 18:59:14
回复(2)
import java.util.*;
public class Solution {
/**
*
* @param A int整型一维数组
* @param target int整型
* @return bool布尔型
*/
public boolean search (int[] A, int target) {
// write code here
if(A == null || A.length <= 0) return false;
int left=0,right = A.length-1;
while(left<=right){
int mid = (left+right)/2;
if(A[mid] == target) return true;
// 如果重复跳过重复再循环一次
if (A[left] == A[mid]) {
left++;
continue;
}
if(A[left] < A[mid]){
if(A[mid]>target && A[left] <= target){
right = mid - 1;
}else{
left = mid + 1;
}
}else{
if(A[mid] < target && A[right] >= target){
left = mid + 1;
}else{
right = mid - 1;
}
}
/*if(A[mid]>=A[right]){
if(A[mid] > target && A[right] <= target){
right = mid - 1;
}else{
left = mid + 1;
}
}else{
if(A[mid] < target && A[left] >= target){
left = mid + 1;
}else{
right = mid - 1;
}
}*/
}
return false;
}
}
编辑于 2020-09-11 16:25:00
回复(0)
class Solution {
public:
/**
* L M R
* |-------|---|-------|
* | 0 1 2 | 4 | 5 6 7 |
* | 7 0 1 | 2 | 4 5 6 |
* T | 6 7 0 | 1 | 2 4 5 |
* | 5 6 7 | 0 | 1 2 4 |
* |-------|---|-------|
* | 4 5 6 | 7 | 0 1 2 |
* B | 2 4 5 | 6 | 7 0 1 |
* | 1 2 4 | 5 | 6 7 0 |
* |-------|---|-------|
*/
bool search(int A[], int n, int target) {
int lo = 0, hi = n - 1;
while(lo <= hi) {
int mid = (lo + hi) >> 1;
if(A[mid] == target) return true;
if(A[mid] < A[hi] && A[mid] < target && target <= A[hi])
lo = mid + 1; // target在T区 且 在M+R区
else if(A[mid] > A[hi] && !(A[lo] <= target && target < A[mid]))
lo = mid + 1; // target在B区 且 不在L+M区
else if(A[mid] == A[hi])
hi = hi - 1;
else
hi = mid - 1;
}
return false;
}
};
发表于 2018-11-18 21:21:12
回复(0)
//有重复元素的情况下，如果A[mid]>A[l]，能确定mid出于左半部，如果A[mid]<A[l]能确定mid
//处于右半部，但是A[mid]==A[l]时，则mid左半部右半部都有可能，因此只能l++遍历。
class Solution {
public:
bool search(int A[], int n, int target) {
int l=0,r=n-1;
while(r>=l){
int mid=l+(r-l)/2;
if(A[mid]==target) return true;
if(A[mid]>A[l]){
if(A[l]<=target&&target<A[mid]) r=mid-1;
else l=mid+1;
}else if(A[mid]<A[l]){
if(A[mid]<target&&target<=A[r]) l=mid+1;
else r=mid-1;
}else l++;
}
return false;
}
};
发表于 2017-08-03 10:23:55
回复(0)
/*
“旋转排序数组搜索”的后续操作：
如果允许重复怎么办？
这会影响运行时的复杂性吗？为什么？
写一个函数以确定给定的目标是否在数组中。
*/ /*
分析：if A[m]>=A[l]不能确定递增，那就把它拆分成两个条件
若A[m]>A[l],则区间[l,m]一定递增
若A[m]==A[l]确定不了，那就l++，往下看一步即可
*/ class Solution {
public:
bool search(int A[], int n, int target) {
int first=0,last=n;
while(first!=last){
int mid=first+(last-first)/2;
if(A[mid]==target)//找到
return true;
if(A[first]<A[mid]){
if(A[first]<=target&&target<A[mid])//缩短区间
last=mid;
else
first=mid+1;
}
else if(A[first]>A[mid]){
if(A[mid]<target&&target<=A[last-1])
first=mid+1;
else
last=mid;
}
else
first++;
}
return false;
}
};
发表于 2017-07-24 09:10:12
回复(0)
http://blog.csdn.net/u011489043 欢迎交流，互相学习
08/25/17修改
class Solution {
public boolean search(int[] nums, int target) {
if(nums.length <= 0)
return false;
int low = 0,high = nums.length - 1;
while(low <= high){
int mid = low + (high - low) / 2;
if(nums[mid] == target)
return true;
if(nums[mid] > nums[high]){//左边有序
if(target >= nums[low] && target < nums[mid])
high = mid - 1;
else
low = mid + 1;
} else if(nums[mid] < nums[high]){//右边有序
if(target > nums[mid] && target <= nums[high])
low = mid + 1;
else
high = mid - 1;
} else // 111101 不能确定哪边有序
high --;
}
return nums[low] == target ? true:false;
}
}
编辑于 2017-08-25 09:32:12
回复(4)
暴力法：
class Solution {
public:
bool search(int A[], int n, int target) {
for(int i=0;i<n;i++)
if(A[i]==target)
return true;
return false;
}
};
二分查找法，重点在于左右边界的确定
整个旋转数组分为两部分一定有一部分有序，那么通过判断左边还是右边有序分为两种情况。
然后再判断向左走还是向右走
当left，middle，right三个值相同默认为左边有序了但是111101
其中0可能出现在左边也可能出现在右边 所以只能遍历
class Solution {
public:
bool search(int A[], int n, int target) {
int first=0;
int last=n-1;
while(first<=last)
{
int mid=first+(last-first)/2;
if(A[mid]==target)
return true;
if(A[first]==A[mid]&&A[mid]==A[last])
{
for(int i=0;i<n;i++)
if(A[i]==target)
return true;
return false;
}
else if(A[first]<=A[mid])//左边有序
{
if(A[first]<=target&&target<A[mid])
last=mid-1;
else
first=mid+1;
}
else if(A[mid]<=A[last])
{
if(A[mid]<target&&target<=A[last])
first=mid+1;
else
last=mid-1;
}
}
return false;
}
};
当left，middle，right三个值相同
默认为左边有序了但是111101
其中0可能出现在左边也可能出现在右边 除了遍历 我们可以把first++ last--缩小范围 总会出现A[first]<=A[mid]或者A[mid]<=A[last]
class Solution {
public:
bool search(int A[], int n, int target) {
int first=0;
int last=n-1;
while(first<=last)
{
int mid=first+(last-first)/2;
if(A[mid]==target)
return true;
if(A[first]==A[mid]&&A[mid]==A[last])
{
first++;
last--;
}
else if(A[first]<=A[mid])//左边有序
{
if(A[first]<=target&&target<A[mid])
last=mid-1;
else
first=mid+1;
}
else if(A[mid]<=A[last])//右边有序
{
if(A[mid]<target&&target<=A[last])
first=mid+1;
else
last=mid-1;
}
}
return false;
}
};
编辑于 2016-07-14 09:49:17
回复(8)
class Solution {
public:
bool search(int A[], int n, int target) {
int l=0,r=n-1;
while(l <= r)
{
int mid = (l+r)/2;
if(A[mid] == target)
return true;
if(A[mid] > A[l])
{
if(A[l] <= target && target <= A[mid])
r = mid - 1;
else
l = mid + 1;
}else if(A[mid] < A[l]){
if(A[mid] < target && target <= A[r])
l = mid + 1;
else
r = mid - 1;
}else
l++;
}
return false;
}
};
发表于 2017-08-09 03:48:17
回复(0)
import java.util.*;
public class Solution {
public boolean search(int[] A, int target) {
if (A == null || A.length == 0)
return false;
if (A[0] < A[A.length - 1])
return Arrays.binarySearch(A, target) >= 0 ? true : false;
for (int i = 0; i < A.length; i++)
if (A[i] == target)
return true;
return false;
}
}
public class Solution {
public boolean search(int[] A, int target) {
if (A == null || A.length == 0)
return false;
if (A[0] < A[A.length - 1])
return Arrays.binarySearch(A, target) >= 0 ? true : false;
for (int i = 0; i < A.length; i++)
if (A[i] == target)
return true;
return false;
}
}
发表于 2020-02-23 16:11:39
回复(0)
class Solution {
public:
bool search(int A[], int n, int target) {
int l = 0;
int r = n - 1;
while (l <= r) {
int m = (l + r) >> 1;
if (A[m] == target) {
return true;
}
if (A[m] == A[l] && A[m] == A[r]) {
l++;
r--;
} else if (A[l] <= A[m]){
if (A[l] <= target && target < A[m]) {
r = m - 1;
} else {
l = m + 1;
}
} else {
if (A[m] < target && target <= A[r]) {
l = m + 1;
} else {
r = m - 1;
}
}
}
return false;
}
};
发表于 2019-11-02 14:10:40
回复(0)
//数组中存在重复元素
//采用二分查找
class Solution {
public:
bool search(int A[], int n, int target) {
if(n==0)
return false;
int l=0,r=n-1;
while(l<=r){
int m=(l+r)/2;
if(A[m]==target)
return true;
else if(A[m]<target){
//右边是排序好的
if(A[m]<=A[r]&&A[r]<target){
//当相等的时候表示有重复，需要单独考虑
if(A[m]==A[r])
r=r-1;
else
r=m-1;
}
else
l=m+1;
}
else{
//左边是排序好的,注意等号
if(A[m]>=A[l]&&target<A[l])
//当相等的时候表示有重复，需要单独考虑
if(A[m]==A[l])
l=l+1;
else
l=m+1;
else
r=m-1;
}
}
return false;
}
};
发表于 2019-06-09 19:52:25
回复(0)
public class Solution {
public boolean search(int[] A, int target) {
int b=0,r=A.length-1;
while(b<=r) {
int mid=b+(r-b)/2;
if(A[mid]==target) return true;
if(A[mid]>A[b]||A[mid]>A[r]){
if(target>=A[b]&&target<A[mid]) {
r=mid-1;
}
else b=mid+1;
}
else if(A[mid]<A[r]||A[mid]<A[b]) {
if(target>A[mid]&&target<=A[r]){
b=mid+1;
}
else r=mid-1;
}
else r--;
}
return false;
}
}
发表于 2019-05-10 10:28:49
回复(0)
//二分法，时间复杂度为O（n)
class Solution {
public:
bool search(int A[], int n, int target) {
if (n == 0) {
return false;
}
int start = 0;
int end = n - 1;
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (target == A[mid]) {
return true;
}
if (A[start] < A[mid]) {
if (A[start] <= target && target < A[mid]) {
end = mid;
} else {
start = mid;
}
} else if (A[start] > A[mid]) {
if (A[mid] < target && target <= A[end]) {
start = mid;
} else {
end = mid;
}
} else {
++start;
}
}
if (A[start] == target || A[end] == target) {
return true;
}
return false;
}
};
发表于 2019-03-06 11:29:14
回复(0)
//做这道题前去做了第一道这题目，解法也写在下边，主要区别就是如果允许重复的元素存在
//那么在判断左右两边哪边有序的时候应该考虑中间元素与最右边比较出现相同的情况
class Solution {
public:
bool search(int A[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (A[mid] == target)
return true;
if (A[mid] < A[right])
{
if (target > A[mid] && target >= A[right])
left = mid + 1;
else
right = mid - 1;
}
else if(A[mid] > A[right])
{
if (target < A[mid] && target <= A[left])
right = mid - 1;
else
left = mid + 1;
}
else
--right;
}
return false;
}
};
#include<iostream>
#include<vector>
using namespace std;
class Solution
{
int search(vector<int>& nums, int target)
{
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] > nums[right])
{
if (nums[mid] < target && nums[right] >= target)
left = mid + 1;
else
right = mid - 1;
}
else
{
if (nums[mid] > target && nums[left] <= target)
right = mid - 1;
else
left = mid + 1;
}
}
return -1;
}
};
发表于 2019-03-03 10:34:33
回复(0)
嗯，估计不会给我offer的
import java.util.Arrays;
public class Solution {
public boolean search(int[] A, int target) {
if(A==null||A.length==0)
{
return false;
}
Arrays.sort(A);
int len=A.length;
int begin=0, end=len-1;
while(begin<=end)
{
int mid=(begin+end)/2;
if(target==A[mid])
{
return true;
}
if(target<A[mid])
{
end=mid-1;
}
if(target>A[mid])
{
begin=mid+1;
}
}
return false;
}
}
发表于 2019-02-19 16:08:30
回复(0)
当A[left] == A[mid] == A[right]时，分别对两边都进行二分查找
其他情况下则判断左边有序还是右边有序，跟之前的问题类似
class Solution {
public boolean search(int[] A, int target) {
return bSearch(A, 0, A.length-1, target);
}
public boolean bSearch(int[] A, int left, int right, int target){
if(left > right) return false;
int mid = (left + right) / 2;
if(A[mid] == target) return true;
if(A[mid] == A[left] && A[mid] == A[right]) return bSearch(A, left, mid-1, target) || bSearch(A, mid+1, right, target);
if(A[left] <= A[mid]){
if(A[left]<=target && target<A[mid])
return bSearch(A, left, mid-1, target);
else
return bSearch(A, mid+1, right, target);
} else {
if(A[mid]<target && target<=A[right])
return bSearch(A, mid+1, right, target);
else
return bSearch(A, left, mid-1, target);
}
}
}
发表于 2018-12-01 22:06:21
回复(0)
class Solution {
public:
bool search(int A[], int n, int target) {
int l = 0, r = n - 1;
if(n == 0)return false;
while(l <= r)
{
int mid = l + (r - l)/2;
if(A[mid] == target)
return true;
if(A[l] < A[mid]) //mid在左侧
{
if(A[l] <= target && target < A[mid])
{
r = mid - 1;
}
else
l = mid + 1;
}
else if(A[l] > A[mid]) //因为是旋转数组，所以mid在右侧
{
if(A[r] >= target && target > A[mid])
{
l = mid + 1;
}
else
r = mid - 1;
}
else //A[mid] == A[l] //无法判断在左边还是右边，只能加加
{
l++;
}
}
return false;
}
};
发表于 2018-08-21 18:19:59
回复(0)
问题信息
难度：
35条回答
88收藏
19838浏览
通过挑战的用户
查看代码-
2022-09-08 12:18:28
-
2022-08-26 15:23:56
-
2022-08-20 15:59:36
-
2022-07-31 00:20:50
-
2022-07-30 12:48:00
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
