在排序的旋转数组中搜索元素


难度级别 中等
经常问 土砖 亚马逊 Apple 彭博 ByteDance 易趣 Expedia的 Facebook 谷歌 微软 Nvidia公司 神谕 贝宝 Paytm VMware的 沃尔玛实验室 Zillow的
排列 二进制搜索

在搜索中按顺序旋转 排列 问题我们提供了一个经过排序和旋转的数组和一个元素,请检查给定元素是否存在于数组中。

例子

输入
nums [] = {2,5,6,0,0,1,2}
目标= 0
输出
true

在排序的旋转数组中搜索元素

输入
nums [] = {2,5,6,0,0,1,2}
目标= 3
输出
false

搜索排序旋转数组中元素的朴素方法

在数组中线性遍历并搜索目标值。

  1. 对i = 0到n(不包括在内)运行一个循环,其中n是数组中元素的数量。
  2. 在每次迭代时,检查nums [i]是否等于目标值。 如果相等,则返回true,否则继续下一个元素。
  3. 如果没有元素等于目标值,则返回false。

JAVA代码

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target) {
        int n = nums.length;
        // Traverse the given array and search for the target value
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;

        System.out.println(searchTarget(nums, target));

        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target));
    }
}
true
false

C ++代码

#include<bits/stdc++.h> 
using namespace std;

bool searchTarget(int *nums, int target, int n) {
    // Traverse the given array and search for the target value
    for (int i = 0; i < n; i++) {
        if (nums[i] == target)
            return true;
    }
    return false;
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

搜索排序旋转数组中元素的复杂度分析

时间复杂度= O(N)
空间复杂度= O(1) 
其中n是数组中元素的数量。

在旋转阵列中搜索元素的最佳方法

该数组可能包含重复项,因此将数组分为两个排序的数组的想法将行不通。

令数组的开始索引为l,结束索引为h,

  1. 找出中点,即中点=(l + h)/ 2。
  2. 如果arr [mid]等于目标值,则返回true。
  3. 如果arr [l]等于arr [h]等于arr [mid],则将l递增,将h递减。
  4. 否则,如果arr [l]小于或等于arr [mid],则对左半部分进行排序,如果目标位于排序的左半部分的范围内,则在左半部分中搜索,在右半部分中搜索。
  5. 如果上述条件不成立,则对从右至中的右半部分进行排序,如果目标位于右半部分的排序范围内,则在右半部分搜索,在左半部分搜索。

JAVA代码

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target, int l, int h) {
        // Index out of bound, element does not exist
        if (l > h)
            return false;
        // Find the middle element
        int mid = (l + h) / 2;
        // If this is the target element, return true
        if (nums[mid] == target) {
            return true;
        }
        // If nums[l] = nums[h] = nums[mid], increment l and decrement h
        if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
            return searchTarget(nums, target, l + 1, h - 1);
        }
        
        // If nums[l] <= nums[mid], left half is sorted
        if (nums[l] <= nums[mid]) {
            // If the target lies in the first half, search in first half
            if (target >= nums[l] && target <= nums[mid]) {
                return searchTarget(nums, target, l, mid - 1);
            }
            // Else search in second half
            return searchTarget(nums, target, mid + 1, h);
        }
        
        // If first half is not sorted, then second half is sorted
        // If the target is present in the second half, search in second half
        if (target >= nums[mid] && target <= nums[h]) {
            return searchTarget(nums, target, mid + 1, h);
        }
        // Else search in the first half
        return searchTarget(nums, target, l, mid - 1);
    }
    
    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;
        
        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
        
        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
    }
}
true
false

C ++代码

#include<bits/stdc++.h> 
using namespace std;

bool searchTarget(int *nums, int target, int l, int h) {
    // Index out of bound, element does not exist
    if (l > h)
        return false;
    // Find the middle element
    int mid = (l + h) / 2;
    // If this is the target element, return true
    if (nums[mid] == target)
        return true;
    // If nums[l] = nums[h] = nums[mid], increment l and decrement h
    if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
        return searchTarget(nums, target, l + 1, h - 1);
    }
    
    // If nums[l] <= nums[mid], left half is sorted
    if (nums[l] <= nums[mid]) {
        // If the target lies in the first half, search in first half
        if (target >= nums[l] && target <= nums[mid]) {
            return searchTarget(nums, target, l, mid - 1);
        }
        // Else search in second half
        return searchTarget(nums, target, mid + 1, h);
    }

    // If first half is not sorted, then second half is sorted
    // If the target is present in the second half, search in second half
    if (target >= nums[mid] && target <= nums[h]) {
        return searchTarget(nums, target, mid + 1, h);
    }
    // Else search in the first half
    return searchTarget(nums, target, l, mid - 1);
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

搜索排序旋转数组中元素的复杂度分析

时间复杂度= O(log n)
空间复杂度= O(1) 
其中n是数组中元素的数量。

參考資料