剑指 Offer 53 - II. 0～n-1 中缺失的数字
找出递增数组中确实的数字；
- 思路：二分查找，看索引与值是否相等，即可找到缺失的数字；相比遍历的方法速度肯定会提升。虽然可以运行，但却难以通过测试。
class Solution:
def missingNumber(self, nums) -> int:
head = 0
tail = len(nums)-1 # 尾端索引应为数组长度减1
m = 0
while head <= tail:
m = (head + tail) //2
if nums[m] == m:
head = m + 1
else:
tail = m -1
return head剑指 Offer 04. 二维数组中的查找
刚开始想法是先通过二分查找第一列去除一些行再对剩余行使用二分查找，但提交时遇到了空矩阵，测试的一直不能通过。直接GG:worried:。
- 解答：将矩阵逆时针旋转45°，转化为图的形式u，类似于二叉搜索树。于是从根节点（可以是最上方也可以是最下方）开始比较目标。如果超界则说明目标不在矩阵中。
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
i, j = len(matrix) - 1, 0
while i >= 0 and j < len(matrix[0]):
if matrix[i][j] > target: i -= 1
elif matrix[i][j] < target: j += 1
else: return True
return False
剑指 Offer 11. 旋转数组的最小数字
从原先升序排列，而后旋转的数组中找出数组中的最小值
- 数组原先是升序的
- 旋转后，整体上升降升
思路：倒序查找，若左边值比当前值大则当前值为最小值；（要考虑到数组为空以及重复元素的问题）
class Solution:
def minArray(self, numbers: List[int]) -> int:
if numbers == [] : return None
index = len(numbers)-1
while index:
if numbers[index] < numbers[index-1]:
return numbers[index]
else:
index = index -1
return numbers[index]答案方法使用二分法，当中点值小于右端点值，则目标值在中点值左侧；当中点值大于右端点值，目标值在右侧。当中点值等于右端点值则无法判断，使右端点左移减少范围。
if numbers == [] : return None
i,j = 0,len(numbers)-1
while i<j:
mid = (i+j)//2
if numbers[mid] < numbers[j]:
j = mid # 这里并没有减去，因为说不定重点就是最小值呢？
elif numbers[mid] > numbers[j]
i = mid + 1
else:
j = j -1
return numbers[i] 
