class Search:
    def __init__(self, input):
        self.list = input
    
    def binary_search(self, min, max, target):
        if min > max:
            return None

        half = (min + max) // 2

        if self.list[half] == target:
            return half
        elif self.list[half] == "":
            # search both side
            found = self.binary_search(min, half -1, target)
            if found == None:
                found = self.binary_search(half + 1, max, target)
            return found
        elif self.list[half] > target:
            return self.binary_search(min, half -1, target)
        
        return self.binary_search(half + 1, max, target)
    
    def search(self, target):
        min = 0
        max = len(self.list) - 1

        return self.binary_search(min, max, target)

# test

input = ["at", "", "", "","ball", "", "", "car", "", "", "dad", "",""]

finder = Search(input)

target = "ball"
found = finder.search(target)

print ("pos for {} = {}".format(target, found))

target = "at"
found = finder.search(target)

print ("pos for {} = {}".format(target, found))


target = "dad"
found = finder.search(target)

print ("pos for {} = {}".format(target, found))


target = "max"
found = finder.search(target)

print ("pos for {} = {}".format(target, found))