4. Median of Two Sorted Arrays

We can use the method that find the k-th samallest element in two sorted list to solve this problem.
In this question, if the total length of this two list is odd, then the median will be the k-th smallest element (len(nums1)+len(nums2))/2
if the total length is even, then the median will be
(l/2-th element + l/2-1-th element)/2
思路就是转换成求两个有序序列中的第k小元素。
如果总长度为偶数，就是求第总长度/2 小的数
如果总长度为奇数，就是求
（第总长度/2 + 第总长度/2 -1）/2
求第K小元素时，
if not n1: return n2[k] if not n2: return n1[k]
先找出两个有序序列的第l/2小的元素，即他们的中位数，将l1 + l2和k比较，如果大于等于k, 就在前半部分找。再继续判断median1和median2的大小，如果m1>m2，我们就舍弃m1的后半段
return self.kthsmall(n1[:l1], n2, k)
否则就舍弃n2的后半段，注意这里K不变，因为舍弃的长度在K之外。
如果l1+l2小于K的话，我们就在后半段找，需要舍弃前边段。
如果m1>m2: return self.kthsmall(n1, n2[l2+1:], k-l2-1)
否则：return self.kthsmall(n1[l1+1:], n2, k-l1-1 )
注意这里要对k进行更新，因为舍弃的长度也包含在k里

33. Search in Rotated Sorted Array

截图来源：code ganker博客

Paste_Image.png

时间复杂度为O(logn)

81. Search in Rotated Sorted Array II

截图来源：code ganker博客

Paste_Image.png

与上一题不同的地方在于这里允许出现重复数字，对边缘进行移动，值到相遇或者边缘的值与mid值不相等：
while left<mid and nums[left]==nums[mid]: left += 1
时间复杂度在最坏情况下变为O(n)

34. Search for a Range

• 循环条件为while left <= right:, 要包含等于，因为可能存在数组里只有1到2个数字这种情况
• 当找到target后，即nums[mid] == target: 此时将mid赋值给两个新的指针，lpivot, rpivot，从mid出发分别朝左右前进，如果
  lpivot >0 and nums[lpivot] == target
rpivot < len(nums) and nums[rpivot] == target
  就继续向左右移动这两个指针，最后返回[lpivot, rpivot]

35. Search Insert Position

循环条件中依然包含等于，原因和上一道题一样。
最后如果target不存在，返回r+1就可以了

50. Pow(x, n)

计算x的n次方。
分几种情况：n==0, n==1, n<0, n%2==0
当n<0时，if n<0: n = -n, x = 1/x，对n, x做相应的变化
if n%2 == 0: return self.myPow(x*x, n/2)
else: return x*self.myPow(x*x, n/2)
因为每次n都变为原来的二分之一，所以总运行时间为O(logn)

69. Sqrt(x)

对x进行二分法，l, r = 0, x
从x的一半开始试：

while l<= r:
         mid = (l+r)/2
         if mid*mid <= x < (mid+1)*(mid+1):
                   return mid
         elif mid*mid > x:
                   r = mid -1
         else:
                   l = mid +1

if mid*mid <= x < (mid+1)*(mid+1): 这句判断的原因是，x有可能不能恰好被开平方，比如10，sqrt(10) = 3

74. Search a 2D Matrix

在一个有序的二维矩阵中找target, 因为这个二维矩阵是有序的，我们依然可以按照最普通的二分查找来做。
m, n = len(matrix), len(matrix[0])
l, r = 0, m*n-1

while l <= r
     mid = (l+r)/2
     num = matrix[mid/n][mid%n]
     if num == target:
        return True

最重要的地方就是如何只根据mid来找到在二维数组中对应的数字。 num = matrix[mid/n][mid%n], n是每一行的元素个数，mid除n可以得到所在的行数，对n取余可以得到所在的列数。
*** if not matrix or target is None: return False
这里不能写matrix is None, 当matrix为[ ]时，就不属于None

153. Find Minimum in Rotated Sorted Array

依然是在rotated array中找值，这次没有给target, 而是让找出最小值，在没有旋转之前，最小值就是第一个值，因为是有序序列。

1. O(n)解法：用for循环遍历数组，找到第一个nums[i] > nums[i+1]时，返回nums[i+1]， 若都不存在，则返回nums[0]，此时证明序列是有序的并且没有被旋转。
2. O(logn)解法：用二分查找来做。

while left <= right:
         if nums[left] < nums[right]:
            return nums[left]
         else:
            mid = (left + right)/2
            if nums[mid] < nums[right]:
               right = mid
            else:
               left = mid + 1
return nums[right]

和其他地方不同的地方在于，这里更新right时不要对mid减1，因为nums[mid]可能就是那个最小的数。如果对right进行mid-1，就会把最小的数给错过。循环终止后返回nums[right]

162. Find Peak Element

peak element就是比左右邻居都大的数，这题默认nums[-1]=nums[n]= 负无穷，题目要求复杂度为log形式，所以依然要用二分法来做。

while left < right:
       mid = (left+right)/2
       if nums[mid] > nums[mid+1]:
          right = mid
       else:
          left = mid+1
return left

比较nums[mid]和nums[mid+1]，如果nums[mid]更大，就对right进行更新，将mid赋值给他。这里不需要mid-1, 因为mid这个元素，可能就是我们要找的peak元素，如果使right = mid-1，就有可能把这个元素给错过去。而left=mid+1是因为nums[mid+1]是那个更大的元素，将Left指向它，就不会错过。
*还有一点需要注意，循环条件不能有等于。有等于的话会循环超时。
*最后可以返回left也可以返回right，因为循环终止时，left=right

209. Minimum Size Subarray Sum

用Sliding window和two pointers可以得到O(n)解法：
left, right均从0开始，维护一个sliding window, 不断累加sum, 当sum>=s时，更新minlen, 并且减去nums[left]，将left向右移动一位，直到sum小于s。然后向右移动一位right，直到right到达数组边界为止。
注意right<len(nums), 是没有等于的，因为要累加nums[right]的值，有等于的话就会数组越界。

left, right, sum, minlen = 0, 0, 0, len(nums)+1
while right < len(nums):
         sum += nums[right]
         while sum >= s:
                 minlen = min(minlen,  right - left +1)
                 sum -= nums[left]
                 left += 1
         right += 1

if len(minlen)==len(nums)+1:
         return 0
else:
        return minlen