My one binary search solution, but the worst case can be O(n)?


  • 0
    L

    The idea is :

    1. Use binary search to find a target
    2. Extend forwards and backwards to find the two boundaries

    But when the list if full of target, e.g. [1,1,1,1,1,1,1,1,1,1] to find "1". This solution can be O(n). Does this meet the requirement?

    class Solution:
        # @param A, a list of integers
        # @param target, an integer to be searched
        # @return a list of length 2, [index1, index2]
        def searchRange(self, A, target):
            start = 0
            end = len(A) - 1
            while start <= end:
                mid = (start + end) / 2
                if A[mid] == target:
                    start = mid
                    end = mid
                    s_mark = False
                    while A[start] == target:
                        if start == 0:
                            s_mark = True
                            break
                        else:
                            start -= 1
                    if s_mark == False:
                        start += 1
                        
                    e_mark = False
                    while A[end] == target:
                        if end == len(A) - 1:
                            e_mark = True
                            break
                        else:
                            end += 1
                    if e_mark == False:
                        end -= 1
                    return [start, end]
                elif A[mid] > target:
                    end = mid - 1
                else:
                    start = mid + 1
            return [-1, -1]

  • 0
    T

    If the list is all 1, the initial search should return true immediately when you check the element at the index in the middle.


  • 0
    L

    You mean I should add some lines to do so? But actually all-1 is just an extreme case, I want to point out that the time complexity will increase with the increasing of number of targets


Log in to reply
 

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