首页 > 试题广场 > 在旋转过的有序数组中寻找目标值
[编程题]在旋转过的有序数组中寻找目标值
  • 热度指数:6490 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个整数数组nums,按升序排序,数组中的元素各不相同。
nums数组在传递给search函数之前,在预先未知的某个下标 t0 <= t <= nums.length-1)上进行旋转,让数组变为[nums[t], nums[t+1], ..., nums[nums.length-1], nums[0], nums[1], ..., nums[t-1]]。
比如,数组[0,2,4,6,8,10]在下标2处旋转之后变为[6,8,10,0,2,4]
现在给定一个旋转后的数组nums和一个整数target,请你查找这个数组是不是存在这个target,如果存在,那么返回它的下标,如果不存在,返回-1
示例1

输入

[6,8,10,0,2,4],10

输出

2
示例2

输入

[6,8,10,0,2,4],3

输出

-1
示例3

输入

[2],1

输出

-1

备注:
1 <= nums.length <= 4000
有序数组查找用二分法,旋转数组关键在于找到有序的那部分,并检查target是否在这有序的部分里面,如果在可以利用二分查找,不在就在另外无序的一部分中查找
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        int left = 0, right = nums.size()-1;
        while(left <= right){
            int mid = (right-left)/2 + left;
            if(nums[mid] == target) return mid;
            if(nums[left] <= nums[mid]){ //[left, mid]有序,在[left, mid]中查找元素
                if(nums[mid] > target && target >= nums[left]){ //target在[left,mid)中则在[left,mid-1]中查找
                    right = mid - 1;
                }
                else{ //target不在[left,mid)中则在[mid+1, right]中查找
                    left = mid + 1;
                }
            }
            else{ //[mid, right]有序,在[mid, right]中查找元素
                if(target > nums[mid] && target <= nums[right]){ //target在(mid, right]中则在(mid, right]中查找
                    left = mid + 1;
                }
                
                else{ //target不在(mid, right]中则在[left, mid-1]中查找
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};












编辑于 2021-05-24 11:27:17 回复(2)
//是我想简单了么,但是可以啊
class Solution {
public:
      int search(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++){
            if(target==nums[i])
                return i;
            else
                continue;
        }
        return -1;
    }
};
发表于 2021-05-25 08:48:13 回复(1)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
发表于 2021-05-17 20:26:08 回复(0)
很简单的二分法,对二分中间值进行判断,如果相等直接返回即可,不相等就二分,要么左边,要么右边,找到一边的条件即可,剩下的归于另一边。
public int search (int[] nums, int target) {
        // write code here
        int left=0;
        int right=nums.length-1;
        int mid=(left+right)>>1;
        while(left<right){
            if(nums[mid]==target){
                return mid;
            }
            if(nums[mid]<target&&target<=nums[right]){
                left=mid+1;
            }else{
                right=mid;
            }
            mid=(left+right)>>1;
        }
        return nums[mid]==target?mid:-1;
    }

发表于 2021-05-10 15:37:27 回复(1)
class Solution:
    def search(self , nums , target):
        # write code here
        if not nums&nbs***bsp;len(nums) == 0:
            return -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right-left)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] >= nums[left]:
                if target >= nums[left] and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if target <= nums[right] and target > nums[mid]:
                    left = mid+1
                else:
                    right = mid-1
        return -1

发表于 2021-06-09 21:28:51 回复(0)
//菜鸡解法
import java.util.*;


public class Solution {
    public int search (int[] nums, int target) {
        if(nums==null || nums.length==0) return -1;
        
        int left = 0, right = nums.length-1;
        if(nums[left]==nums[right]) {
            if(target==nums[left]) return left;
            left++;
            while(left<right && nums[left-1]==nums[left]) left++;
            right--;
            while(left<right && nums[right]==nums[right+1]) right--;
        }
        
        int mid = left + (right-left)/2;
        while(left<right) {
            if(nums[mid]==target) return mid;
            else if(nums[left]<=nums[mid]) {
                if(nums[mid]>target && target>=nums[left]) right = mid-1;
                else left = mid+1;
            }
            else if(nums[mid]<=nums[right]) {
                if(nums[mid]<target && target<=nums[right]) left = mid+1;
                else right = mid-1;
            }
            mid = left + (right-left)/2;
        }
        
        return nums[mid]==target? mid: -1;
    }
}

发表于 2021-06-07 16:55:59 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        if(nums==null||nums.length==0){
            return -1;
        }
        if(nums.length==1){
            return nums[0]==target?0:-1;
        }
        int loc;
        for(loc = 1;loc<nums.length;++loc){
            if(nums[loc-1]>nums[loc]){
                break;
            }
        }
        if(loc==nums.length){
            return binarySearch(nums,0,loc-1,target);
        }
        
        int res;
        if(target>=nums[0]){
            res = binarySearch(nums,0,loc,target);
        }else{
            res = binarySearch(nums,loc,nums.length-1,target);
        }
        return res;
    }
    
    private int binarySearch(int[] arr,int start,int end,int target){
        int mid;
        while(start<=end){
            mid = start+(end-start)/2;
            if(arr[mid]==target){
                return mid;
            }else if(arr[mid]>target){
                end = mid -1;
            }else{
                start = mid +1;
            }
        }
        return -1;
    }
}

发表于 2021-06-04 19:56:29 回复(0)
先找到旋转的位置,把数组切分成两个升序的子数组,再判断target与数组的第一位的大小来判断target存在哪个子数组中,确定了子数组之后再用二分法求出target的位置。
发表于 2021-06-02 20:11:49 回复(0)
这个题的测试用例不够全。
我的代码有bug,
运行用例,
[10,0,2,4],10 
返回-1,
却可以通过。
发表于 2021-05-25 22:52:58 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        //1.最简单的,顺序遍历,找到就返回下标
//         for(int i=0;i<nums.length;i++){
//             if(nums[i]==target){
//                 return i;
//             }
//         }
//         return -1;
        
        
        //2.想想二分法,因为这道题涉及到升序排列后的旋转,以及寻找元素,所以,可以使用二分法的思想
        //关键在于找到有序的那一部分,并且根据判断条件缩小二分区间
        int low = 0;
        int high = nums.length-1;
        while(low<=high){
            int mid = low+(high-low)/2;
            if(nums[mid]==target){return mid;}
            //在区间[low,mid]是有序的
            if(nums[mid]>=nums[low]){
                //target在[low,mid-1]中
                if(nums[mid]>target && target>=nums[low]){high=mid-1;}
                //target在[mid+1,high]中
                else{low=mid+1;}
            }
            //在区间[mid,high]是有序的
            else{
                //target在[mid+1,high]中
                if(nums[mid]<target && target<=nums[high]){low=mid+1;}
                //target在[low,mid-1]中
                else{high=mid-1;}
            }
        }
        return -1;
    }
}
发表于 2021-05-24 11:07:40 回复(0)
又醉了。。。 用二分竟然只超过2%的人。 。我这个是标准的左右闭合区间的2分。 。 。 很容易记
public int search (int[] nums, int target) {
        int left = 0, right = nums.length -1;
        while (left <= right){
            int mid = left + (right - left) /2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid -1;
            }else if(nums[mid] < target){
                left = mid +1;
            }
        }
        return -1;
    }


发表于 2021-05-19 11:10:23 回复(0)
题目绕了半天和旋转有什么关系?
发表于 2021-05-14 15:47:41 回复(0)
有序旋转数组,二分法
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        if(nums.size() == 0) return -1;
        if(nums.size() == 1) return nums[0] == target ? 0 : -1;
        
        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)
                    left = mid + 1;
                else
                    right = mid - 1;
            }else{
                if(nums[mid] < target)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
        }
        return -1;
    }
};
未知旋转次数的旋转数组查找,返回下表最小值
class Solution {
public:
    int search(vector<int>& nums, int target) {
        // write code here
        if(nums.size() == 0) return -1;
        if(nums.size() == 1) return nums[0] == target ? 0 : -1;
        
        int left = 0, right = nums.size() - 1;
        int index = -1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            //判断边界是否是
            if(nums[left] == target)
                {index = left; break;}
            else if(nums[right] == target)
                {index = right; break;}
            else if(nums[mid] == target)
                {index = mid; break;}

            if(nums[left] < nums[mid])//左边有序,但是目标可能存在其中
            {
                if(nums[left] < target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;

            }else if(nums[mid] < nums[right])//右边有序
            {
                if(nums[mid] < target && target < nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }else{
                left++;
                right--;
            }
        }
       
        if(index != -1)//查找下标最小值
        {
            while(index >= 0 && nums[index] == target)
                --index;
            index += 1;
        }
        return index;
    }
};



编辑于 2021-05-13 20:29:52 回复(0)
public int search (int[] nums, int target) {
        // write code here
        int l = 0;
        int r = nums.length-1;
        while(l<=r){
            int mid = (r-l)/2+l;
            if(nums[mid]==target)
                return mid;
            if(nums[mid]<=nums[l] && nums[mid]<=nums[r]){ //如果是左小右大
                if(nums[mid]>target)
                    r = mid-1;
                else
                    l = mid+1;
            }else{
                // 4 5 6 1 2 3
                if(nums[mid]<target){  //往大的方向挪动
                    if(nums[mid]>nums[l])
                        l=mid+1;
                    else{
                        if(target>nums[r])
                            r=mid-1;
                        else
                            l=mid+1;
                    }
                }else{//往小的方向挪动
                    if(nums[mid]>nums[l]){
                        if(target <nums[l])
                            l=mid+1;
                        else
                            r=mid-1;
                    }
                    else{
                        r=mid-1;
                    }
                }
            }
        }
        return -1;
    }

发表于 2021-05-11 17:12:15 回复(0)
import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        // write code here
        int l = 0,h = nums.length - 1;
        while(l <= h){
            int m = (h + l)/2;
            if(nums[m] == target) return m;
            if(nums[l] == target) return l;
            if(nums[h] == target) return h;
            //m在右端
            if(nums[m] < nums[h]) {
                if(target > nums[m] && target < nums[h]) l = m + 1;
//                 else if(target > nums[m] && target > nums[h]) h = m - 1;
                else h = m - 1;
            //m在左端
            }else {
                if(nums[l] < target && target < nums[m]) h = m - 1;
//                 else if(nums[l] > target && target < nums[m]) l = m + 1;
                else l = m + 1;
            }
        }
        return -1;
    }
}

发表于 2021-05-07 20:04:17 回复(0)
二分查找思想
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left >> 1);
            if (nums[mid] == target) return mid;
            // 如果 0 ~ mid 有序
            if (nums[0] <= nums[mid]) {
                // 如果 target 在这 0 ~ mid 的有序下标中 则在这个区间二分,否则一定在另一个区间
                if (target >= nums[0] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                //同上
                if (target <= nums[nums.length - 1] && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
}


发表于 2021-05-07 13:41:20 回复(0)

int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        //先找出最小值的坐标
        while(left < right)
        {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] > nums[right])
                left = mid + 1;
            else if(nums[mid] < nums[right])
                right = mid;
            else
                right = right - 1;
        }
        if(target <= nums[nums.size() - 1])
            right = nums.size() - 1;
        else
            left = 0;
        while(left <= right)
        {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid - 1;
            else
                return mid;
        }
        return -1;
    }

发表于 2021-05-02 12:34:16 回复(0)
import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        // write code here
        int left = 0, right = nums.length-1;
        // 先找到left和right的索引,right的索引需要加上数组长度
        for(int i = 0; i < nums.length-1; i++){
            if(nums[i+1] < nums[i]){
                left = i+1;
                right = i+nums.length-1;
                break;
            }
        }
        while(left <= right){
            int mid = left + (right-left)/2;
            if(nums[mid%nums.length] == target)
                return mid%nums.length;
            else if(nums[mid%nums.length] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        if(nums[left%nums.length] == target)
            return left%nums.length;
        else 
            return -1;
    }
}
发表于 2021-04-30 13:50:33 回复(0)
    public int search (int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target)
                return i;
        }
        return -1;
    }

发表于 2021-04-29 14:20:27 回复(1)
HashMap 
先将数组里的数以值为关键字,下标为保存值;
利用count函数,若关键字target存在,count返回1,输出哈希表中的值。若不存在 count输出0,返回-1;
int search(vector<int>& nums, int target) {
        // write code here
        unordered_map<int, int>mymap;
        for(int i=0;i<nums.size();i++)
            mymap[nums[i]]=i;
        if(mymap.count(target)!=0)
            return mymap[target];
        return -1;
    }
发表于 2021-04-27 16:36:43 回复(1)