Какова временная сложность моего решения?

Question

Сценарий:

У меня есть метод, называемый «searchRange», где мне нужно искать для минимального и максимального индекса, где целевой происходит в подаваемом входном массиве.

Вопрос:

Я думаю, что временная сложность этого решения является O (п), потому что я зацикливание над входом только один раз. Правильно ли я понимаю?

Код:

public class Solution { 

    public int[] searchRange(int[] nums, int target) { 
     if (nums == null) { 
      return new int[2]; 
     } 
     int min = -1, max = -1, l = nums.length; 
     int[] ans = new int[2]; 
     for (int i = 0; i < l; i++) { 
      if (nums[i] == target) { 
       if (min == -1) { 
        min = i; 
       } else { 
        max = Math.max(i, max); 
       } 
      } 
     } 
     if (min != -1 && max == -1) { 
      max = min; 
     } 
     ans[0] = min; 
     ans[1] = max; 
     return ans; 
    } 
} 

EDIT

Спасибо, теперь я знаю, что временная сложность выше алгоритма O (п). Я пытаюсь достичь O (logn). Я попытался использовать вариант бинарного поиска, чтобы обнаружить индексы min и max. Является ли временная сложность метода, приведенного ниже O (logn)?

public int[] searchRange(int[] nums, int target) { 
    if (nums == null) 
     return new int[2]; 
    return searchRange(nums, target, 0, nums.length - 1); 
} 

public int[] searchRange(int[] nums, int target, int l, int h) { 
    int[] ans = new int[] { -1, -1 }; 
    int middle = (l + h)/2; 
    if (l > h) 
     return ans; 
    if (nums[middle] == target) { 
     if (middle < nums.length - 1 && nums[middle + 1] == target) { 
      int[] right = searchRange(nums, target, middle + 1, h); 
      ans[1] = right[1]; 
      ans[0] = middle; 
     } 
     if (middle >= 1 && nums[middle - 1] == target) { 
      int[] left = searchRange(nums, target, l, middle - 1); 
      ans[0] = left[0]; 
      if (ans[1] == -1) { 
       ans[1] = middle; 
      } 
     } 
     if (ans[0] == ans[1] && ans[0] == -1) { 
      ans[0] = ans[1] = middle; 
     } 
    } else if (nums[middle] < target) { 
     return searchRange(nums, target, middle + 1, h); 
    } else { 
     return searchRange(nums, target, l, middle - 1); 
    } 
    return ans; 
} 

Answer 1

Похож на простой O (n), где n - длина вашего входного массива. Вы будете перебирать весь массив при каждом вызове функции searchRange().