二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。其基本思想是将待查找的键值与数组中间的元素进行比较，如果两者相等，则查找成功；如果待查找的键值小于中间元素，则在数组的左半部分继续查找；如果待查找的键值大于中间元素，则在数组的
摘要：二分查找 (1) 搜索插入位置 """ 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
二分查找
(1) 搜索插入位置
"""
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
"""
left = 0
right = len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] < target:
left = mid+1
else:
right = mid-1
return left
(2) 在排序数据中查找元素范围
"""
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
"""
def get_index(nums, target):
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] < target:
left = mid+1
else:
right = mid-1
return left
if target not in nums:
return [-1, -1]
start = get_index(nums, target)
end = get_index(nums, target+1)-1
return [start, max(start, end)]
(3) 搜索旋转排序数组
"""
整数数组 nums 按升序排列，数组中的值互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2]。给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1。
"""
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid-1
else:
left = mid+1
else:
if nums[mid] < target <= nums[right]:
left = mid+1
else:
right = mid-1
return -1
(4) 寻找旋转排序数组的最小值
"""
给你一个元素值 互不相同 的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素 。
"""
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] >= nums[0]:
left = mid+1
else:
right = mid-1
return nums[left] if left < len(nums) else nums[0]
(5) 寻找两个正序数组的中位数
"""
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
"""
m, n = len(nums1), len(nums2)
total = m+n
i = j = 0
prev = cur = 0
for _ in range(total//2+1):
prev = cur
if i < m and (j >= n or nums1[i] < nums2[j]):
cur = nums1[i]
i += 1
else:
cur = nums2[j]
j += 1
if total%2 == 1:
return cur
return (prev+cur)/2
栈
(1) 有效的括号
"""
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效
"""
dic = {"(": ")", "{": "}", "[": "]", "?": "?"}
stack = ["?"]
for c in s:
if c in dic:
stack.append(c)
elif dic[stack.pop()] != c:
return False
return len(stack) == 1
(2) 字符串解码
"""
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
"""
stack, res, multi = [], "", 0
for char in s:
if char == "[":
stack.append([multi, res])
res, multi = "", 0
elif char == "]":
cur_multi, last_res = stack.pop()
res = last_res + cur_multi*res
elif '0' <= char <= '9':
multi = multi*10 + int(char)
else:
res += char
return res
(3) 每日温度
"""
给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
"""
n = len(temperatures)
res = [0] * n
stack = []
for i in range(n-1, -1, -1):
t = temperatures[i]
while stack and t >= temperatures[stack[-1]]:
stack.pop()
if stack:
res[i] = stack[-1]-i
stack.append(i)
return res
(4) 柱状图中最大的矩形
堆
(1) 数组中第 k 个最大元素
"""
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
"""
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
(2) 前 k 个高频元素
"""
给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。
"""
counts = collections.Counter(nums)
return [item[0] for item in counts.most_common(k)]
(3) 数据流的中位数
class MedianFinder:
def __init__(self):
self.A = [] # 最小堆
self.B = [] # 最大堆
def addNum(self, num: int) -> None:
if len(self.A) != len(self.B):
heapq.heappush(self.A, num)
heapq.heappush(self.B, -heapq.heappop(self.A))
else:
heapq.heappush(self.B, -num)
heapq.heappush(self.A, -heapq.heappop(self.B))
def findMedian(self) -> float:
return self.A[0] if len(self.A) != len(self.B) else (self.A[0]-self.B[0])/2.0