LC28 Implement strStr()

class Solution:
    def myPow(self, x: float, n: int) -> float:
    #time O(lgN) space O(1)
        res = 1.0
        if n < 0:
            x = 1/x
            n *= -1
        while n:
            # check if n is odd number 
            if n & 1 :
                res *= x
            x *= x 
            n >>=  1
        return res

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n < 0:
            return 1/self.rec(x,-n)
        return self.rec(x,n)
    def rec(self,a,b):
        if b == 0:
            return 1
        half = self.rec(a,b//2)
        if b%2 == 0:
            return half *half
        else: 
            return half *half * a