Постановка задачи

Имеется целочисленный массив nums, отсортированный в неубывающем порядке (не обязательно с разными значениями).

Перед передачей в вашу функцию nums поворачивается на неизвестный опорный индекс k (0 ‹= k ‹ nums.length) таким образом, что результирующий массив: [nums[k], nums[k + 1], …, nums[n — 1], nums[0], nums[1], …, nums[k — 1]] (0-индексировано). Например, [0, 1, 2, 4, 4, 4, 5, 6, 6, 7] можно повернуть с опорным индексом 5 и превратить в [4, 5, 6, 6, 7, 0, 1, 2, 4, 4].

Учитывая массив nums после поворота и целое число target, верните true, если target находится в nums, или false, если оно не в nums.

Вы должны максимально сократить общие шаги операции.

Постановка задачи взята с: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/.

Пример 1:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
Output: true

Пример 2:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
Output: false

Ограничения:

- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5

Объяснение

Решение этой задачи аналогично предыдущему Поиск в отсортированном массиве с чередованием. Единственная разница заключается в том, что из-за наличия дубликатов возможно nums[low] == nums[mid], и мы должны рассматривать этот случай отдельно.

Перейдем непосредственно к алгоритму.

// search function
- if low > high
    - return -1
- set mid = low + (high - low) / 2
- if nums[mid] == key
    - return true
- if nums[low] == nums[mid + 1] && nums[high] == nums[mid]
    - low++
    - high--
    - search(nums, low, high, key)
if nums[low] <= nums[mid]
    - if key >= nums[low] && key <= nums[mid]
        - return search(nums, low, mid - 1, key)
    - return search(nums, mid + 1, high, key)
if key >= nums[mid] && key <= nums[high]
    - return search(nums, mid + 1, high, key)
- return search(nums, low, mid - 1, key)

Давайте проверим наши решения на C++, Golang и Javascript.

С++ решение

class Solution {
public:
    bool searchUtil(vector<int>& nums, int low, int high, int target) {
        if(low > high) {
            return false;
        }
        int mid = low + (high - low)/2;
        if(nums[mid] == target){
            return true;
        }
        if(nums[low] == nums[mid] && nums[high] == nums[mid]){
            low++;
            high--;
            return searchUtil(nums, low, high, target);
        }
        if(nums[low] <= nums[mid]){
            if(target >= nums[low] && target <= nums[mid]){
                return searchUtil(nums, low, mid - 1, target);
            }
            return searchUtil(nums, mid + 1, high, target);
        }
        if(target >= nums[mid] && target <= nums[high]){
            return searchUtil(nums, mid + 1, high, target);
        }
        return searchUtil(nums, low, mid - 1, target);
    }
    bool search(vector<int>& nums, int target) {
        bool result = searchUtil(nums, 0, nums.size() - 1, target);
        return result;
    }
};

Голанг решение

func searchUtil(nums []int, low, high, target int) bool {
    if low > high {
        return false
    }
    mid := low + (high - low) / 2
    if nums[mid] == target {
        return true
    }
    if nums[low] == nums[mid] && nums[high] == nums[mid] {
        low++
        high--
        return searchUtil(nums, low, high, target)
    }
    if nums[low] <= nums[mid] {
        if target >= nums[low] && target <= nums[mid] {
            return searchUtil(nums, low, mid - 1, target)
        }
        return searchUtil(nums, mid + 1, high, target)
    }
    if target >= nums[mid] && target <= nums[high] {
        return searchUtil(nums, mid + 1, high, target);
    }
    return searchUtil(nums, low, mid - 1, target);
}
func search(nums []int, target int) bool {
    return searchUtil(nums, 0, len(nums) - 1, target)
}

Javascript-решение

var searchUtil = function(nums, low, high, target) {
    if(low > high) {
        return false;
    }
    let mid = low + (high - low)/2;
    if(nums[mid] == target){
        return true;
    }
    if(nums[low] == nums[mid] && nums[high] == nums[mid]){
        low++;
        high--;
        return searchUtil(nums, low, high, target);
    }
    if(nums[low] <= nums[mid]){
        if(target >= nums[low] && target <= nums[mid]){
            return searchUtil(nums, low, mid - 1, target);
        }
        return searchUtil(nums, mid + 1, high, target);
    }
    if(target >= nums[mid] && target <= nums[high]){
        return searchUtil(nums, mid + 1, high, target);
    }
    return searchUtil(nums, low, mid - 1, target);
};
var search = function(nums, target) {
    return searchUtil(nums, 0, nums.length - 1, target);
};

Давайте обработаем проблему всухую.

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
// search function
Step 1: searchUtil(nums, 0, nums.size() - 1, target)
        searchUtil(nums, 0, 6, 0)
// searchUtil function
Step 2: low > high
        0 > 6
        false
Step 3: mid = low + (high - low)/2
            = 0 + (6 - 0)/2
            = 0 + 6/2
            = 3
Step 4: if nums[mid] == target
           nums[3] == 3
           0 == 3
           false
Step 5: if nums[low] == nums[mid] && nums[high] == nums[mid]
           nums[0] == nums[3] && nums[6] == nums[3]
           2 == 0 && 2 == 0
           false
Step 6: if nums[low] <= nums[mid]
           nums[0] <= nums[3]
           2 <= 0
           false
Step 7: if target >= nums[mid] && target <= nums[high]
           3 >= nums[3] && 3 <= nums[6]
           3 >= 0 && 3 <= 2
           false
Step 8: searchUtil(nums, low, mid - 1, target)
        searchUtil(nums, 0, 2, 3)
// searchUtil function
Step 9: low > high
        0 > 2
        false
Step 10: mid = low + (high - low)/2
             = 0 + (2 - 0)/2
             = 0 + 2/2
             = 1
Step 11: if nums[mid] == target
            nums[1] == 3
            5 == 3
            false
Step 12: if nums[low] == nums[mid] && nums[high] == nums[mid]
            nums[0] == nums[1] && nums[2] == nums[1]
            2 == 5 && 6 == 5
            false
Step 13: if nums[low] <= nums[mid]
            nums[0] <= nums[1]
            2 <= 5
            true
            if target >= nums[low] && target <= nums[mid]
               3 >= nums[0] && 3 <= nums[1]
               3 >= 2 && 3 <= 5
               true
               return searchUtil(nums, low, mid - 1, target)
                      searchUtil(nums, 0, 1 - 1, 3)
                      searchUtil(nums, 0, 0, 3)
// searchUtil function
Step 14: if low > high
            0 > 0
            false
Step 15: mid = low + (high - low)/2
             = 0 + (0 - 0)/2
             = 0 + 0/2
             = 0
Step 16: if nums[mid] == target
            nums[0] == 3
            2 == 3
            false
Step 17: if nums[low] == nums[mid] && nums[high] == nums[mid]
            nums[0] == nums[0] && nums[0] == nums[0]
            2 == 2 && 2 == 2
            true
            low++
            low = 1
            high--
            high = -1
            return searchUtil(nums, low, high, target)
                   searchUtil(nums, 1, -1, 3)
// searchUtil function
Step 14: if low > high
            1 > -1
            true
            return false
// We go back from Step 14 to Step 9 to Step 2 to Step 1 because of recursion
We return the answer as false.

Первоначально опубликовано на https://alkeshghorpade.me.