What would be the time complexity of Search Range problem solution DnC

Viewed 53

I would appreciate some help in figuring out the time complexity of the solution for Search Range problem from leetcode which involves recursion and DnC algorithm.

I am not sure whether it is O(N) or O(NlogN) and why?

func searchRange(nums []int, target int) []int {
    if (len(nums) == 0) {
      return []int{-1, -1}
    }
    return helper(nums, target, 0, len(nums) - 1)
}
func helper(nums []int, target, start, end int) []int {
    res := []int {-1, -1}
    if (nums[start] > target || nums[end] < target || start > end || (start == end && nums[start] != target)) {
      return res
    }
    
    if (start == end) {
      res[0] = start
      res[1] = end
      return res
    }
    mid := (start + end) / 2
    res1 := helper(nums, target, start, mid)
    res2 := helper(nums, target, mid + 1, end)
    if (res1[0] == -1) {
      return res2
    }
    if (res2[0] == -1) {
      return res1
    }
    res[0] = res1[0]
    res[1] = res2[1]
    return res
}
0 Answers
Related