首页 > 试题广场 >

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

[编程题]在旋转过的有序数组中寻找目标值
  • 热度指数:41149 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
有一个长度为 n 的按严格升序排列的整数数组 nums ,在实行 search 函数之前,在某个下标 k 上进行旋转,使数组变为[nums[k],nums[k+1],.....,nums[nums.length-1],nums[0],nums[1],.......,nums[k-1]]。
给定旋转后的数组 nums 和一个整型 target ,请你查找 target 是否存在于 nums 数组中并返回其下标(从0开始计数),如果不存在请返回-1。

数据范围:
要求:空间复杂度 ,时间复杂度

比如,数组[0,2,4,6,8,10]在下标3处旋转之后变为[6,8,10,0,2,4], 当给定target为10时,10的下标是2,target为3时,nums数组中不存在3,所以返回-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 回复(5)

1.利用HashMap

import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        // write code here
        HashMap<Integer,Integer> hm = new HashMap<>();
        for(int i =0; i<nums.length; i++){
            hm.put(nums[i],i);
        }
        Arrays.sort(nums);
        int left = 0, right= nums.length-1;
        while(left<=right){
            int mid = left+(right - left)/2;
            if(nums[mid] == target) return hm.get(nums[mid]);
            if(nums[mid] > target)right = mid-1;
            if(nums[mid] < target)left = mid+1;
        }
        return -1;
    }
}

2.直接二分

import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        // write code here
        int lo=0,hi=nums.length-1;
        while(lo <= hi){
            int mid = lo+ (hi-lo)/2;
            if(nums[mid] == target) return mid;
            if(nums[mid] <nums[hi] && nums[mid]<target && target<=nums[hi])
                lo = mid+1;
            else if(nums[mid] >nums[hi] &&!( nums[lo] <=target && target < nums[mid]))
                lo = mid+1;
            else
                hi = mid-1;
        }
        return -1;
    }
}


编辑于 2021-04-26 11:39:16 回复(8)
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)
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 l = 0;
        int r = nums.length - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return nums[l] == target ? l : -1;
    }
}

发表于 2021-08-21 19:48:35 回复(2)
不就是在给定的数组中判断有没有这个元素么,前面的铺垫都是屁话,忽悠人呢。
发表于 2021-06-19 19:21:39 回复(5)
//是我想简单了么,但是可以啊
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 回复(9)
    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)
菜鸟随便写的
int search(int* nums, int numsLen, int target ) {
    // write code here
    int l = 0;
    int r = numsLen-1;
    while(l<=r) {
        int mid = l + (r-l)/2;
        if(nums[mid]==target) {
            return mid;
        }
        if(nums[mid]>=nums[0]) {
            if(target<nums[mid]&&target>=nums[0]) {
                r=mid-1;
            }
            else {
                l=mid+1;
            }
        }
        else {
            if(target>nums[mid]&&target<nums[0]) {
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }
    }
    return -1;
}
发表于 2023-10-09 17:16:52 回复(0)
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        return -1 if target not in nums else nums.index(target)

发表于 2023-07-24 10:48:55 回复(0)
package main

// 找出旋转点,然后左右分别二分查找
func search(nums []int, target int) int {
	//找出旋转点,即最小值
	left, right := 0, len(nums)-1
	for left < right {
		mid := (left + right) / 2
		if nums[mid] > nums[right] { //旋转点必定在右侧(不包括mid,因为旋转点为最小值,这里mid已经比right大了)
			left = mid + 1
		} else if nums[mid] < nums[left] { //旋转点必定在左侧(包括mid)
			right = mid
		} else { //这里的隐式条件是(nums[left]<=nums[mid]<=nums[right])只能确定最右侧一定不是旋转点
			right--
		}
	}
	//旋转点即为left
	res := find(nums[:left], target)
	if res != -1 {
		return res
	}
	res = find(nums[left:], target)
	if res != -1 {
		return res + left
	}
	return -1
}

func find(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (left + right) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

发表于 2023-06-05 11:13:58 回复(0)
```cpp
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @param target int整型
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        int leftNum = nums[0];
        int rightNum = nums.back();
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midNum = nums[mid];
            if (midNum == target) {
                return mid;
            }
            if (midNum >= leftNum) {
                if (target < midNum && target >= rightNum) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (midNum <= rightNum) {
                if (target > midNum && target <= rightNum) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

```
发表于 2023-06-04 19:57:13 回复(0)
三次二分查找即可
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */

    int binSearch(vector<int> nums, int l, int r, int target){
        if(l > r)   return -1;
        int mid = (l+r) / 2;
        if(nums[mid] == target) return mid;
        else if (nums[mid] < target)  return binSearch(nums, mid + 1, r, target);
        else if (nums[mid] > target) return binSearch(nums, l, mid - 1, target);
        return -1;
    }

    int binSearch(vector<int> nums, int l, int r){
        if(l > r)   return 0;
        int mid = (l+r) / 2;
        if(mid + 1 >= nums.size())  return 0;
        if(nums[mid] > nums[mid + 1]) return mid;
        else if (nums[mid] > nums[r])  return binSearch(nums, mid + 1, r);
        else if (nums[mid] < nums[l]) return binSearch(nums, l, mid - 1);
        return 0;
    }
    
    int search(vector<int>& nums, int target) {
        int index = binSearch(nums, 0, nums.size()-1);
        return max(binSearch(nums, 0, index, target), binSearch(nums, index+1, nums.size()-1, target));
    }
};

发表于 2023-04-23 10:58:13 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        
        for(int i=0; i<=nums.size()-1; i++)
        {
            if(nums[i]==target)
            {
                return i;
            }
            
            
        }
        
        return -1;
        
        
        
        // write code here
    }
};
发表于 2023-04-22 21:08:45 回复(0)
/*
思路:二分搜索

既然数据旋转过,说明数组是如下情况:

4567 123

数组分为两部分,左半部分递增,右半部分递增,在中间有个低谷,低谷是最小元素。

因为是严格升序,因此不考虑有相同元素的情况

设置三个指针,左,中,右。

如果中指针指向的元素大于左指针,则此区间有序
当区间有序,如果目标值大于区间最大值,该区间被舍弃。左指针指向中指针
如果目标值小于区间最大值,那么中

中指针指向的元素小于右指针,则此区间有序
当区间有序,如果目标值大于区间最大值,该区间被舍弃。右指针指向中指针


当一个区间无序,另一个必定有序

234 5671

左半边有序,右半边无序,那么就去左半边找。


*/
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        if(nums.size()==0){
            return -1;
        }

        int result = -1;

        int left = 0;
        int right = nums.size()-1;
        int mid = (left+right)/2;

        while(left<=right){
            mid = (left+right)/2;
            //相等直接返回
            if(nums[mid] == target){
                result = mid;
                break;
            }
            //判断左半边是否有序
            if(nums[left]<nums[mid]){
                if(target>nums[mid] || target<nums[left]){
                    //目标大于左半边最大值 或 小于左半边最小值
                    left = mid+1;
                    continue;
                }else{
                    //目标值在这个区间
                    right = mid-1;
                    continue;
                }
            }else{
                //左半边无序,右半边必然有序
                if(target>nums[right] || target<nums[mid]){
                    //目标值大于右半边最大值 或 小于右半边最小值
                    right = mid-1;
                    continue;
                }else{
                    //目标值在这个区间
                    left = mid+1;
                    continue;
                }
            }
        }
        return result;
    }
};

发表于 2023-04-12 21:51:31 回复(0)
package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
*/
func search( nums []int ,  target int ) int {
    i,j:=0,len(nums)-1
    for i<j{
        if nums[i]==target{
            return i
        }
        if nums[j]==target{
            return j
        }
        i++
        j--
    }
    if i==j&&nums[i]==target{
        return i
    }
    return -1
}

发表于 2023-01-25 11:21:43 回复(0)
public int search (int[] nums, int target) {
    // write code here
    int p1=0 ,p2=nums.length-1;
    while(p1<=p2){
        int mid=(p1+p2)/2;
        if(nums[mid]==target){
            return mid;
        }else if(target<nums[mid]){
            if(nums[mid]>=nums[p1]){
                if(target<nums[p1]){
                    p1=mid+1;
                }else{
                    p2=mid-1;
                }
            }else{
                p2=mid-1;
            }
        }else{
            if(nums[p2]>=nums[mid]){
                if(nums[p2]>=target){
                    p1=mid+1;
                }else{
                    p2=mid-1;
                }
            }else{
                p1=mid+1;
            }
        }
    }
    return -1;
}

发表于 2022-12-30 22:45:20 回复(0)

使用二分法,不过需要先遍历一遍数组,找到旋转点,确定好target在旋转点的左侧还是右侧,再在该侧中使用二分法查找即可

int search(int* nums, int numsLen, int target ) {
    // write code here
    if(numsLen>0) {
        int left=0, right=numsLen-1;
        for(int i=0; i<numsLen; i++) {
            if(nums[i+1]<nums[i]){
                printf("nums[i]:%d\n",nums[i]);
                if(nums[i]>=target&&target>nums[0]) right=i;
                else if(nums[i]==target) return i;
                else left=i+1;
                break;
            }
        }
        printf("left:%d, right:%d\n",left,right);
        while(left<=right) {
            int mid = left+(right-left)/2;
            if(nums[mid]==target) return mid;
            if(nums[mid]<target) left=mid+1;
            if(nums[mid]>target) right=mid-1;
        }
    }
    return -1;
}
发表于 2022-11-10 10:13:57 回复(0)
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            # 左半部分有序
            if nums[mid] >= nums[left]:
                if target > nums[mid]:
                    left = mid+1
                else:
                    if nums[left] == target:
                        return left
                    elif nums[left] > target:
                        left = mid+1
                    else:
                        right = mid-1
            # 右半部分有序
            else:
                if target < nums[mid]:
                    right = mid-1
                else:
                    if nums[right] == target:
                        return right
                    elif nums[right] < target:
                        right = mid-1
                    else:
                        left = mid+1
        return -1

发表于 2022-07-26 20:43:14 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        int len=nums.size();
        int i=0,j=len-1;
        while(i<j){
            int m=(i+j)/2;
            if(nums[m]<nums[j]){
                if(nums[m]<target&&target<=nums[j]){
                    i=m+1;
                }
                else{
                    j=m;
                }
            }
            else if(nums[m]>=nums[j]){
                if(nums[i]<=target&&target<=nums[m]){
                    j=m;
                }
                else{
                    i=m+1;
                }
            }
        }
        return nums[i]==target?i:-1;
    }
};

发表于 2022-07-03 09:51:23 回复(0)
import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        // 用哈希暂存当前的标号
        HashMap<Integer,Integer> hm = new HashMap<>();
        for(int i =0; i<nums.length; i++){
            hm.put(nums[i],i);
        }
        //重新排序
        Arrays.sort(nums);
        //二分查询
        int x1 = Arrays.binarySearch(nums, target);
        if(x1<0){
            return -1;
        }else{
            return hm.get(nums[x1]);
        }
    }
}

发表于 2022-06-24 12:20:47 回复(0)