Algorithm Post: Binary Search - Search for a range

search_for_a_range.py

class BinarySearch:
    @staticmethod
    def find_first_position(arr, target):
        st, ed = 0, len(arr) - 1
        while st + 1 < ed:
            mid = (st + ed) / 2
            if arr[mid] == target:
                ed = mid
            elif arr[mid] < target:
                st = mid
            else:
                ed = mid
        if arr[st] == target:
            return st
        if arr[ed] == target:
            return ed
        return -1
    
    @staticmethod
    def find_last_position(arr, target):
        st, ed = 0, len(arr) - 1
        while st + 1 < ed:
            mid = (st + ed) / 2
            if arr[mid] == target:
                st = mid
            elif arr[mid] < target:
                st = mid
            else:
                ed = mid
        if arr[ed] == target:
            return ed
        if arr[st] == target:
            return st
        return -1
        
if __name__ == '__main__':
    arr = [1, 2, 3, 3, 3, 4, 5]
    print(BinarySearch.find_first_position(arr, 3))
    print(BinarySearch.find_last_position(arr, 3))