Ptyhon O(logn) solution using BS


  • 0
    T

    The idea behind my solution is to use Binary Search in order to figure out the left and right bound indices. The down side is it seems it violates DRY principle. Any ideas to remove de duplication but still keep it simple and readable?

    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):
            left_bound = self.find_left(A, target)
            right_bound = self.find_right(A, target)
            
            return [left_bound, right_bound]
            
        def find_left(self, a, k):
            if not a: return -1
            
            start = 0
            end = len(a) - 1
            
            while start <= end:
                mid = (start + end) / 2
                if a[mid] == k:
                    if mid == 0 or a[mid - 1] != k:
                        return mid
                    end = mid - 1
                elif a[mid] > k:
                    end = mid - 1
                else:
                    start = mid + 1
            return -1
            
        def find_right(self, a, k):
            if not a: return -1
            
            start = 0
            end = len(a) - 1
            
            while start <= end:
                mid = (start + end) / 2
                if a[mid] == k:
                    if mid == (len(a) - 1) or a[mid + 1] != k:
                        return mid
                    start = mid + 1
                elif a[mid] > k:
                    end = mid - 1
                else:
                    start = mid + 1
            return -1

Log in to reply
 

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