내 솔루션의 복잡성은 얼마나됩니까?

Question

시나리오 :

제가 목표 제공된 입력 어레이에서 발생하는 최소 및 최대 인덱스를 검색해야 "searchRange"이라 불리는 방법이있다.

는 질문 :

은 내가 한 번만 입력을 통해 반복하고 있기 때문에이 솔루션의 시간 복잡도는 O (N)라고 생각합니다. 내 이해가 맞습니까?

코드 :

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; 
    } 
} 

편집

덕분에, 지금은 위의 알고리즘의 시간 복잡도는 O (n)이 있음을 알고있다. 나는 O (logn)쪽으로 접근하려고 노력하고있다. 최소 및 최대 인덱스를 발견하기 위해 이진 검색 변형을 사용하려고했습니다. 이 방법의 시간 복잡도는 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

는 N이 입력 배열의 길이 간단한 O (N)처럼 보인다. searchRange() 함수를 호출 할 때마다 전체 배열을 반복합니다.