Binary Search

[Uber]LC 34 Find First and Last Position of Element in Sorted Array
找一个target 在排序数组中出现多少次，最后问了一下复杂度和corner case。

LB: first element >=target
UB: first element >target

class Solution(object):
    def searchRange(self, nums, target):
        if not nums: return [-1,-1]
        LB = self.find_LB(nums,target)
        UB = self.find_UB(nums,target)
        return [LB,UB]
    
    def find_LB(self,nums,target):
        l,r = 0,len(nums)
        while l<r:
            mid = l + (r-l)//2
            if nums[mid]<target:
                l = mid + 1
            else:
                r = mid
        if l>=len(nums) or l<0: return -1
        return l if nums[l]==target else -1
    
    def find_UB(self,nums,target):
        l,r = 0,len(nums)
        while l<r:
            mid = l + (r-l)//2
            if nums[mid]>target:
                r = mid
            else:
                l = mid+1
        if r-1>=len(nums) or r-1<0: return -1
        return r-1 if nums[r-1]==target else -1

[Uber] 154 Find Minimum in Rotated Sorted Array II
mid 如果小于右端点，就可以划掉右半段。

[Uber]LC685
如果输入数组不是sorted该怎么解决，接下来问的是如果输入的数组已经排好序了，可以怎么用更小的时间复杂度解决这个问题。
要求优化到 two pointer!
如果不是sorted ，可不可以用一个size 为K 的max heap来保存一下tuple，compartor 比较的是每个数和target的绝对值。这样空间换时间?

LC 50 Pow(x,n)
Recursion很好写，interative的话，怎么理解每当遇到奇数的时候，就要把当前累计的pow放入ans?
power n变化过程:11--5--2--1
x的变化过程x--x^2--x4--x^8
奇数对应的累乘就是ans = xx^2x^8=x11

    def myPow(self, x, n):
        if n==0: return 1
        if x==0: return 0
        if n<0: 
            n=-n
            x = 1/x
        return x*self.myPow(x*x,n//2) if n&1 else self.myPow(x*x,n//2)

    def myPow(self, x, n):
        if n==0: return 1
        if x==0: return 0
        if n<0: 
            n=-n
            x = 1/x
        ans = 1
        while n:
            if n&1: #odd
                ans *=x
            x*=x
            n=n>>1
        return ans