leetcode: 34. Search for a Range

# Given an array of integers sorted in ascending order, 
# find the starting and ending position of a given target value.
#
# Your algorithm's runtime complexity must be in the order of O(log n).
#
# If the target is not found in the array, return [-1, -1].
#
# For example,
# Given [5, 7, 7, 8, 8, 10] and target value 8,
# return [3, 4].

class Solution():
    def searchRange(self, x, target):
        loc = self.binarySearch(x, target)
        if loc >= len(x) or x[loc] != target:
            return [-1, -1]
        l = r = loc
        while l > 0 and x[l-1] == x[loc]:
            l -= 1
        while r < len(x)-1 and x[r+1] == x[loc]:
            r += 1
        return [l, r]
    def binarySearch(self, x, target):
        l, r = 0, len(x) - 1
        while l <= r:
            mid = (l + r) // 2
            if x[mid] == target:
                return mid
            elif x[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return l


if __name__ == "__main__":
    assert Solution().searchRange([1], 1) == [0, 0]
    assert Solution().searchRange([1, 2, 3], 1) == [0, 0]
    assert Solution().searchRange([2, 2], 3) == [-1, -1]
    assert Solution().searchRange([5, 7, 7, 8, 8, 10], 8) == [3, 4]