Leetcode # 33 Превышен предел времени - PullRequest
0 голосов
/ 27 мая 2020

https://leetcode.com/problems/search-in-rotated-sorted-array/

Вопрос требует, чтобы решение было O (log n), и я считаю, что мое решение - O (log n), поскольку мой процесс поиска наименьшего элемента равно O (log n), а затем использование двоичного поиска для поиска целевого значения также O (log n). Однако мой код превышает лимит времени.

int search(vector<int>& nums, int target) {
    if(nums.size() == 0){
        return -1;
    }
    int left = 0;
    int right = nums.size() - 1;
    while(left < right){
        int middle = left + (right - left) / 2;
        if(nums[left] < nums[middle]){
            left = middle;
        }
        else{
            right = middle;
        }
    }
    if(target >= nums[0]){
        return binarySearch(nums, target, 0, left - 1);
    }
    else{
        return binarySearch(nums, target, left, nums.size() - 1);
    }
}

int binarySearch(vector<int>& nums, int target, int start, int end){
    if(nums.size() == 0 || (start == end && nums[start] != target)){
        return -1;
    }
    int mid = start + (end - start) / 2;
    if(nums[mid] == target){
        return mid;
    }
    if(nums[mid] > target){
        return binarySearch(nums, target, start, mid - 1);
    }
    else{
        return binarySearch(nums, target, mid, end);
    }
}

1 Ответ

1 голос
/ 27 мая 2020

Я считаю, что binarySearch может столкнуться с бесконечным l oop. Когда end = start + 1 вы получите mid = start, поэтому, если nums [start]

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...