81. Search in Rotated Sorted Array II

leetcode medium

#array#csharp#leetcode#medium#search#sort#two-pointers

Task

В массиве целых чисел 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 в противном случае.

Необходимо сократить количество операций поиска настолько, насколько это возможно.

Пример:

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

Output: true

C# solution

matched/original

public class Solution {
    public bool Search(int[] nums, int target) {
        if (nums.Length == null)
            return false;
        int end = nums.Length - 1;
        int start = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target)
                return true;
            if (nums[start] == nums[mid] && nums[end] == nums[mid]) {
                start++;
                end--;
            } else if (nums[start] <= nums[mid]) {
                if (nums[start] <= target && target < nums[mid])
                    end = mid - 1;
                else
                    start = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[end])
                    start = mid + 1;
                else
                    end = mid - 1;
            }
        }
        return false;
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool Search(vector<int>& nums, int target) {
        if (nums.size() == null)
            return false;
        int end = nums.size() - 1;
        int start = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target)
                return true;
            if (nums[start] == nums[mid] && nums[end] == nums[mid]) {
                start++;
                end--;
            } else if (nums[start] <= nums[mid]) {
                if (nums[start] <= target && target < nums[mid])
                    end = mid - 1;
                else
                    start = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[end])
                    start = mid + 1;
                else
                    end = mid - 1;
            }
        }
        return false;
    }
}

Java solution

matched/original

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return false;
        int end = n - 1;
        int start = 0;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                return true;
            }

            if (!isBinarySearchHelpful(nums, start, nums[mid])) {
                start++;
                continue;
            }

            boolean pivotArray = existsInFirst(nums, start, nums[mid]);
            boolean targetArray = existsInFirst(nums, start, target);
            if (pivotArray ^ targetArray) {
                if (pivotArray) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                if (nums[mid] < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return false;
    }

    private boolean isBinarySearchHelpful(int[] arr, int start, int element) {
        return arr[start] != element;
    }

    private boolean existsInFirst(int[] arr, int start, int element) {
        return arr[start] <= element;
    }
}

JavaScript solution

matched/original

var search = function (nums, target) {
    let n = nums.length;
    if (n == 0) return false;
    let end = n - 1;
    let start = 0;
    while (start <= end) {
        let mid = start + Math.floor((end - start) / 2);
        if (nums[mid] == target) {
            return true;
        }
        if (!isBinarySearchHelpful(nums, start, nums[mid])) {
            start++;
            continue;
        }
        let pivotArray = existsInFirst(nums, start, nums[mid]);
        let targetArray = existsInFirst(nums, start, target);
        if (pivotArray ^ targetArray) {
            if (pivotArray) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        } else {
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return false;
};

function isBinarySearchHelpful(nums, start, element) {
    return nums[start] != element;
}

function existsInFirst(nums, start, element) {
    return nums[start] <= element;
}

Python solution

matched/original

class Solution:
    def search(self, nums, target):
        n = len(nums)
        if n == 0:
            return False
        end = n - 1
        start = 0
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return True
            if not self.isBinarySearchHelpful(nums, start, nums[mid]):
                start += 1
                continue
            pivotArray = self.existsInFirst(nums, start, nums[mid])
            targetArray = self.existsInFirst(nums, start, target)
            if pivotArray ^ targetArray:
                if pivotArray:
                    start = mid + 1
                else:
                    end = mid - 1
            else:
                if nums[mid] < target:
                    start = mid + 1
                else:
                    end = mid - 1
        return False

    def isBinarySearchHelpful(self, nums, start, element):
        return nums[start] != element

    def existsInFirst(self, nums, start, element):
        return nums[start] <= element

Go solution

matched/original

func search(nums []int, target int) bool {
    n := len(nums)
    if n == 0 {
        return false
    }
    end := n - 1
    start := 0
    for start <= end {
        mid := start + (end-start)/2
        if nums[mid] == target {
            return true
        }
        if !isBinarySearchHelpful(nums, start, nums[mid]) {
            start++
            continue
        }
        pivotArray := existsInFirst(nums, start, nums[mid])
        targetArray := existsInFirst(nums, start, target)
        if pivotArray != targetArray {
            if pivotArray {
                start = mid + 1
            } else {
                end = mid - 1
            }
        } else {
            if nums[mid] < target {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    }
    return false
}

func isBinarySearchHelpful(nums []int, start int, element int) bool {
    return nums[start] != element
}

func existsInFirst(nums []int, start int, element int) bool {
    return nums[start] <= element
}

Explanation

Algorithm

1️⃣

Вспомним стандартный бинарный поиск, где мы используем два указателя (start и end), чтобы отслеживать область поиска в массиве arr. Затем мы делим пространство поиска на три части: [start, mid), [mid, mid], (mid, end]. Далее мы продолжаем искать наш целевой элемент в одной из этих зон поиска.

2️⃣

Определяя положение arr[mid] и target в двух частях массива F и S, мы можем сократить область поиска так же, как в стандартном бинарном поиске:

Случай 1: arr[mid] находится в F, target в S: так как S начинается после окончания F, мы знаем, что элемент находится здесь: (mid, end].

Случай 2: arr[mid] находится в S, target в F: аналогично, мы знаем, что элемент находится здесь: [start, mid).

Случай 3: Оба arr[mid] и target находятся в F: поскольку оба они находятся в той же отсортированной части массива, мы можем сравнить arr[mid] и target, чтобы решить, как сократить область поиска.

Случай 4: Оба arr[mid] и target находятся в S: так как оба они в той же отсортированной части массива, мы также можем сравнить их для решения о сокращении области поиска.

3️⃣

Однако, если arr[mid] равен arr[start], то мы знаем, что arr[mid] может принадлежать и F, и S, и поэтому мы не можем определить относительное положение target относительно mid. В этом случае у нас нет другого выбора, кроме как перейти к следующей области поиска итеративно. Таким образом, существуют области поиска, которые позволяют использовать бинарный поиск, и области, где это невозможно.

😎