My 8 lines accepted solution in Ruby, time complexity is log(n). Is it right?


  • 0
    A
    # analyze T(n)
    #  If (may) have cut,   this program will search left and right part two. But one part without cut will only check once.
    #  The part may have cut will check both sides, but the cutting point is only one. So, the time complexity is also o(log(n))
    #  Is my analysis right?
    def search(nums, target)
      return nums.include?(target) if nums.size<4
      m=(nums.size-1)/2
      return true if nums[m]==target
      return search(nums[0..m-1], target)||search(nums[m+1..-1], target) if nums[m]<=nums[0]||nums[m]>=nums[-1] #may have cut
      return search(nums[0..m-1], target) if nums[m] > target
      return search(nums[m+1..-1], target) if nums[m] < target
    end
    

    In comment I post my analysis, thanks for your attention!


  • 2
    Y

    may be not
    thinking out 1 11 1 1 1 1 11


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.