首页 > 试题广场 >

在转动过的有序数组中寻找目标值

[编程题]在转动过的有序数组中寻找目标值
  • 热度指数:34764 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给出一个转动过的有序数组,你事先不知道该数组转动了多少
(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).
在数组中搜索给出的目标值,如果能在数组中找到,返回它的索引,否则返回-1。
假设数组中不存在重复项。
示例1

输入

[1],0

输出

-1
示例2

输入

[3,2,1],1

输出

2
推荐
暴力求解
class Solution {
public:
    int search(int A[], int n, int target) {
        for(int i=0;i<n;i++)
            if(A[i]==target)
                return i;
         return -1;
    }
};

二分查找法,重点在于左右边界的确定
整个旋转数组分为两部分一定有一部分有序,那么通过判断左边还是右边有序分为两种情况。
然后再判断向左走还是向右走
class Solution {
public:
    int 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 mid;
            
            if(A[first]<=A[mid])//左边有序
            {
                if(A[first]<=target&&target<A[mid])
                    last=mid-1;
                else
                    first=mid+1;
            }
            else//右边有序
            {
                 if(A[mid]<target&&target<=A[last])
                     first=mid+1;
                 else
                     last=mid-1;
                    
            }
        }
        
        return -1;
        
    }
};
感觉可以  你就给个赞

编辑于 2016-07-24 10:09:39 回复(11)
class Solution {
public:
    // 不要被“旋转”而迷惑,“有序”并不是二分查找的核心
    // 二分查找的核心是"通过界桩快速决定查找方向,大幅缩短查找空间"
    // 只要能快速确定界桩,就能使用二分查找
    // 充分利用有序数组能够快速获取边界值的特性
    // 利用这一特性可以快速确定目标值应处的区间
    int search(vector<int>& nums, int target) {
        if (nums.empty())
            return -1;
        int lo = 0, hi = nums.size() - 1;
        
        while (lo <= hi) {
            int mi = lo + ((hi - lo) >> 1);
            if (nums[mi] == target)
                return mi;
            
            // 只要在普通的二分查找判断语句中加一层 && 来确定目标值所在的区间,即可以同样O(logn)的复杂度查找
            if (nums[lo] <= nums[mi] && (nums[lo] <= target && target < nums[mi]))
                hi = mi - 1;
            else if (nums[mi] <= nums[hi] && !(nums[mi] < target && target <= nums[hi]))
                hi = mi - 1;
            else
                lo = mi + 1;
        }
        return -1;
    }
};

发表于 2019-04-03 21:25:32 回复(4)

好喜欢暴力搜索啊。

发表于 2018-07-04 10:36:22 回复(2)
  • 先判断是否发生旋转,判断旋转的依据就是数组的第一个值大于最后一个值。
  • 如果没有发生旋转,直接用二分查找
  • 如果发生了旋转,找出旋转点,确定了两个有序的子数组,然后在有序的子数组中进行二分查找。while循环结束,begin对应的是最大值,end对应的是最小值。
public class Solution {
    public int search(int[] A, int target) {
        if(A == null || A.length == 0){
            return -1;
        }
        int begin = 0;
        int end = A.length - 1;
        if(A[begin] < A[end]){
            return binarysearch(A, begin, end, target);
        }else{
            while(A[begin] > A[end]){
                if(end - begin == 1){
                    break;
                }
                int mid = (begin + end)/2;
                if(A[mid] > A[begin]){
                    begin = mid;
                }else{
                    end = mid;
                }
            }

            if(target >= A[0]){
                return binarysearch(A, 0, begin, target);
            }else{
                return binarysearch(A, begin+1, A.length - 1, target);
            }
        }

    }

    public int binarysearch(int[] A, int begin, int end, int target){
        if(A == null || A.length == 0){
            return -1;
        }
        while(begin <= end){
            int mid = (begin + end)/2;
            if(A[mid] > target){
                end = mid - 1;
            }else if(A[mid] < target){
                begin = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}
发表于 2016-12-14 22:16:01 回复(2)
把所有旋转情况列出来,可以发现T区的MR区,和B区的LM区,都是有序的,代码简洁明了。

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 |
     *   |-------|---|-------|
     */

    int 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 mid;
            
            if(A[mid] < A[hi] && A[mid] < target && target <= A[hi])
                lo = mid + 1;  // target在T区 且 在L+M区
            else if(A[mid] > A[hi] && !(A[lo] <= target && target < A[mid]))
                lo = mid + 1;  // target在B区 且 不在L+M区
            else 
                hi = mid - 1;
        }
        return -1;
    }
};

编辑于 2018-11-18 17:41:32 回复(5)

对旋转数组进行均等划分后,总有一边是有序的,如:

  1. 10 11 12 13 14 15 1 2 3
  2. 10 11 15 1 2 3 4 5 6 7 8

我们定位到有序的一边后,对比target与有序子数组的左右边界,就可以作出搜索左侧还是右侧的决策。

代码如下:

第16行必须是<=,不能是<,举例——从[3,1]中查找1

//
// Created by jt on 2020/9/3.
//
class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @param target int整型
     * @return int整型
     */
    int search(int* A, int n, int target) {
        // write code here
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) return mid;
            if (A[mid] >= A[left]) {
                // 左侧有序(含A[mid])
                if (A[mid] > target && A[left] <= target)
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                // 右侧有序(含A[mid])
                if (A[mid] < target && A[right] >= target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }
};
编辑于 2020-09-03 17:48:14 回复(1)
这个示例二没问题嘛?
发表于 2020-11-24 22:35:29 回复(3)
class Solution {
public:
    // 二分查找
    int search(int A[], int n, int target)
    {
        int left = 0,middle,right = n-1;
        while(left <= right)
        {
           middle = (right+left)>>1;
           if(A[middle] == target)
                return middle;
           if(A[left] <= A[middle])  /// left side is sorted
           {
               if(A[left] <= target && target < A[middle])
                   right = middle-1;
               else
                   left = middle+1;
           }
           else                     /// right side is sorted
           {
               if(A[middle] < target && target <= A[right])
                    left = middle+1;
               else
                    right = middle-1;
           }
        }
        return -1;
    }
};

发表于 2017-07-08 21:00:53 回复(2)
1、二分查找思路
2、先确定A是否整体有序
3、无序,则必定可分为前一个大数组,后一个小数组,只需找出分界索引即可
class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return int整型
     */
   int search(int* A, int n, int target) {
        // write code here
        if(A[0]>A[n-1])
        {
            int mid=n/2;
            if(A[0]<A[mid])
            {
                while(A[0]<A[mid]&&mid<(n-1))
                {
                    mid++;
                }
            }
            else
            {
                while(A[0]>A[mid])
                {
                    mid--;
                }
            }
            if(target>=A[0])
                return binarySearch(A, 0, mid, target);
            else
               return binarySearch(A, mid+1, n-1, target);

        }
        else
        {
            return binarySearch(A, 0, n-1, target);
        }
    }
    
    int binarySearch(int *A,int start,int end,int target)
    {
        if(target==A[start])
            return start;
        if(target==A[end])
            return  end;
        if(start==end||(start+1)==end)
            return -1;
        if(A[(start+end)/2]==target)
            return (start+end)/2;
        if(A[(end+start)/2]<target)
        {
            return binarySearch(A, (end+start)/2,  end, target);
        }
        else
        {
            return binarySearch(A, start, (end+start)/2, target);
        }
    }
    

};


发表于 2021-03-21 22:07:36 回复(0)
class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return int整型
     */
    int search(int* A, int n, int target) {
        // write code here
        int left=0;int right=n-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(A[mid]==target)  return mid;
            if(A[mid]<=A[right])
            {
                if(target>A[mid]&&target<=A[right])  left=mid+1;
                else  right=mid-1;
            }
            else 
            {
                if(target<A[mid]&&target>=A[left])  right=mid-1;
                else  left=mid+1;
            }
        }
        if(A[left]==target)  return left;
        else  return -1;
    }
};

发表于 2021-01-13 21:53:22 回复(0)
看评论很多直接二分,但是发现 [1,2,3,4,5,6,0];0 这组数据是找不到的
感觉是应该先找到二分的断点,分成两部分,分别进行二分法
但是这里已经耗费了 平均n/2的时间 再加上 lon2(n)  可能和直接找差不多
求个更便捷的方法

int search(int* A, int n, int target) {
        // write code here
        int res = -1;
        for(int i = 0; i < n; i++)
        {
            if(A[i] == target)
            {
                 res = i;
                 break;
            }  
        }
        return res;
    }
发表于 2020-12-22 09:26:31 回复(1)
题解的关键在 “二分” 而不是 “旋转” ,二分就是利用当前条件来判断下一次的边界在哪里,管他有没有旋转,条件是足够的!

Step 1、 和普通有序数列二分一样,左右边界依旧是 0 和 length-1,中点是 (左+右)/ 2;
Step 2、 判断中点值是否为目标值,若是的话直接返回,若不是 开始判断下一个我们找的区域在左边还是右边。
Step 3、若A[]>=A[左],说明中点左边的序列是有序的,有序好办了,判断一下目标值和两个边界的大小,若目标值在这个区间内,下一次循环就在左边的区域;若不在则下次循环就在右边的区域。
Step 4、若A[中]<A[左],说明中点右边的序列是有序的(跟上一步道理相同,这一点想通了就好说了,可以根据例子来理解),同样,有序的话就很容易判断目标值在不在这个区域内,从而得出下次循环的区域。
重复2、3、4。
上代码:
import java.util.*;
public class Solution {

    public int search (int[] A, int target) {

        int left_point = 0;
        int right_point = A.length-1;   
        int mid;
       
        while(left_point<=right_point){
            mid = (left_point + right_point)/2;
            if (A[mid] == target)
                return mid;
            
            if (A[mid]>=A[left_point]){//左边区域有序
                if(target>A[left_point]&&target<A[mid]){                    
                 right_point = mid; //左边找  
                  
                 }else{
                   left_point = mid+1;//右边找
                 }
            }
            else{//右边区域有序
                if(target<A[right_point]&&target>A[mid]){                   
                    left_point = mid+1;//右边找
                }
                else{                    
                    right_point = mid;//左边找                    
                }
            }
        }
        return -1;    
  }
}


发表于 2020-11-23 22:21:18 回复(2)
试想一下,在一个旋转后的有序数组中,利用中间元素作为切分点得到的两个子数组有什么样的性质。
经过枚举不难发现,这两个子数组中,一定存在一个数组是有序的
也可能出现一个特殊情况,二者都是有序的。

对于有序的一边,我们是很容易判断目标值,是否在这个区间内的。
如果在其中,也说明了目标值不在另一边的旋转有序组里;反之亦然。

当我们知道了目标值在左右哪边之后,就可以递归地调用旋转有序的二分查找了。
之所以可以递归调用,是因为,对于旋转有序组,这个问题二分后的解法与有序数组没有旋转的情况完全一样。
对于有序组,它是旋转有序的特殊情况(即旋转 0 位),也一定是可以通过递归的方法去实现查找的。
直到不断二分后,搜索空间只有 1 个数字,直接判断是否找到即可。

import java.util.*;

public class Solution {
    private static int bs(int[] arr, int target, int begin, int end) {
    if (begin == end) {
        if (target == arr[begin]){
            return begin;
        }
        else{
            return -1;
        }
    }
    int middle = begin + (end - begin)/2;
    if (target == arr[middle]) {
        return middle;
    }
    /* if array only has 2 numbers */
    if (middle == begin) {
        if (target == arr[end]) {
            return end;
        }
        else {
            return -1;
        }
    }
    if (arr[begin] <= arr[middle-1]){
        if (arr[begin] <= target && target <= arr[middle-1]) {
            return bs(arr,target, begin,middle-1);
        } else {
            return bs(arr,target, middle+1,end);
        }
    }
    else {
        if (arr[middle+1] <= target && target <= arr[end]) {
            return bs(arr,target, middle+1,end);
        } else {
            return bs(arr,target, begin,middle-1);
        }
    }
}
    /**
     * 
     * @param A int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] A, int target) {
        return bs(A, target, 0, A.length-1);
    }
}


发表于 2020-11-21 18:26:01 回复(0)
判断target在中间的左边还是右边。判断某边时,需判断是在左边有序还是右边有序(若存在)中。
class Solution { public:     /**      *       * @param A int整型一维数组       * @param n int A数组长度      * @param target int整型       * @return int整型      */     int search(int* A, int n, int target) {         // write code here         int left = 0, right = n;         while(left < right) {             int m = (left) + ((right-left)>>1);             if(A[m] == target) return m;             if(A[left] <= A[m] && !(A[left] <= target && target < A[m])){                 left = m+1;             }             else if(A[left] > A[m] && (A[m] < target && target <= A[right-1])) {                 left = m+1;             }             else                  right = m;                      }         return -1;     } };

编辑于 2020-10-24 05:25:11 回复(0)
方法一
class Solution {
public:
    int search(int A[], int n, int target) {
        map<int,int>m;
        if(target==A[0])
            return 0;
        for(int i=0;i<n;i++)
            m[A[i]]=i;
        return m[target]>0?m[target]:-1;
    }
};

方法二
class Solution {
public:
    int search(int A[], int n, int target) {
        for(int i=0;i<n;i++)
            if(target==A[i])
                return i;
        return -1;
    }
};

发表于 2019-05-18 19:41:42 回复(0)
class Solution {
public:
    int search(int A[], int n, int target) {
		int l = 0,h = n-1;
		while(l <= h)
		{
			int mid = (l+h)/2;
			if(A[mid] == target)
				return mid;
			if(A[l] <= A[mid])
			{
				if(A[l] <= target && target <= A[mid])
					h = mid - 1;
				else
					l = mid + 1;
			}else{
				if(A[mid] <= target && target <= A[h])
					l = mid + 1;
				else
					h = mid - 1;
			}
		}
		return -1;
    }
};

发表于 2017-08-06 02:53:22 回复(0)
public class Solution {
    public int search(int[] A, int target) {
		int position = 0;
		for (int i = 1; i < A.length; i ++) {
			if(A[i] < A[i - 1]) position = i - 1;
		}
		int search1 = binarySearch(A, 0, position, target);
		int search2 = binarySearch(A, position + 1, A.length - 1, target);
		if(search1 == - 1 && search2 == - 1) return - 1;
		return search1 == - 1 ? search2 : search1;
	}
	public int binarySearch(int[] arr, int low, int high, int target) {
		while (low <= high) {
			int mid = (low + high) / 2;
			if(arr[mid] < target) low = mid + 1;
			else if(arr[mid] > target) high = mid - 1;
			else return mid;
		}
		return - 1;
	}
}

编辑于 2017-03-26 18:10:04 回复(0)
//题意:经过一次旋转的有序数组中,找到target数,并返回其位置
//使用二分查找,先找出有序数组分界点,如果target大于第一个数,则在左半边二分查找,反之在右边二分查找。
//分界点即数组最小点,亦可二分查找left,right逐步确定分界点(若是重复数组,只能乖乖顺序查找分界点)
public class Solution {
    public int search(int[] A, int target) {
        int left=0;
        int right=A.length-1;
        if(left==right){
            if(A[0]==target)
                return 0;
            else
                return -1;
        }
        int mid;
        while(left<right-1){//为了寻找分界点
            mid=(right-left)/2+left;// 直接使用(high + low) / 2 可能导致溢出
            if(A[mid]>A[left]){
                left=mid;
            }
            if(A[mid]<A[right]){
                right=mid;
            }            
        }
        int min=right;//得出分界点
        if(A[0]<=target){//在(第一点到分界点)左半部分二分查找
            left=0;
            right=min-1;
            while(left<=right){
                mid=(right-left)/2+left;
                if(A[mid]==target){
                    return mid;
                }
                else if(A[mid]>target){
                    right=mid-1;
                }
                else{
                    left=mid+1;
                }
            }
        }
        if(A[A.length-1]>=target){//在(分界点到最后一点)右半部分二分查找
            left=min;
            right=A.length-1;
            while(left<=right){
                mid=(right-left)/2+left;
                if(A[mid]==target){
                    return mid;
                }
                else if(A[mid]>target){
                    right=mid-1;
                }
                else{
                    left=mid+1;
                }
            }
        }           
        return -1;
    }
}

发表于 2016-10-20 23:09:18 回复(1)

二分查找法,重点在于左右边界的确定
发表于 2016-06-27 15:40:20 回复(0)
二分查找
整个旋转数组分为两部分一定有一部分有序,那么通过判断左边还是右边有序分为两种情况。
然后再判断向左走还是向右走
public class Solution {
    public int search(int[] A, int target) {
        int left = 0,right = A.length-1,middle;
    while(left<=right){
    middle = (right+left)/2;
    if(target==A[middle]){
    return middle;
    }
    if(A[middle]<A[A.length-1]){//右边有序
    if(target>A[middle] && target<=A[A.length-1]){
    left = middle+1;
    }else{
    right = middle-1;
    }
    }else{//左边有序
    if(A[0]<=target && target<A[middle]){
    right = middle-1;
    }else{
    left = middle+1;
    }
    }
    }
        return -1;
    }
}
发表于 2016-03-14 09:47:58 回复(0)
public class Solution {
    public int search(int[] a, int target) {
        int len=a.length;
        if(len==0){
            return -1;
        }
        int low=0;
        int high=len-1;
        int mid=0;
        while(low<=high){
            mid=(low+high)/2;
            if(a[mid]==target){
                return mid;
            }
            //判断是正常的排序顺序
            if(a[low]<=a[high]){
                if(a[mid]>target){
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }
            //否则就是存在旋转的排序
            else{
                //判断左边有序(low直到mid 有序,a[low]是左边最小值,a[mid]是左边序列的最大值)
                if(a[low]<=a[mid]){
                    //如果target介于a[low]与a[mid]之间,就在左边找
                   if(target>=a[low]&&target<a[mid]){
                       high=mid-1;
                   }else{
                       low=mid+1;
                   }
                }
                //判断右边有序,(mid直到high有序)
                else{
                    //如果target介于a[mid]与a[high]之间,就在右边找
                    if(target>a[mid]&&target<=a[high]){
                        low=mid+1;
                    }else{
                        high=mid-1;
                    }
                }
            }
        }
        return -1;
    }
}

发表于 2019-02-12 14:34:40 回复(0)