'''
    Solution to the activity question. 
    Re-write the iterative binary search as a recursive one
    '''
    def _search( self, key ):
        """Search for the key and returns the index if found, returns
        -1 if not found.
        Since the list is sorted, we can do binary search"""

        l = len( self._table ) - 1
        return self._dbinsearch( 0, l, key )
        
    def _dbinsearch( self, first, last, key ):
        """Binary search to find the index of the key"""
        if first > last:
            return -1   # not found

        mid = first + ( last - first ) // 2
        if self._table[ mid ].key < key : # search the second half
            return self._dbinsearch( mid+1, last, key )
        elif self._table[ mid ].key > key : # search the first half
            return self._dbinsearch( first, mid-1, key )
        else:
            return mid   # found it!