一.二分法 | KWAN的解忧杂货铺

# 一.二分法

# 1.二分法

Python 实现二分查找的模板代码：

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            # 找到目标值，进行相应的操作
            return mid
        elif nums[mid] < target:
            # 目标值在右边
            left = mid + 1
        else:
            # 目标值在左边
            right = mid - 1
    # 没有找到目标值
    return -1
 
        Copied!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这是一种常用的二分查找模板，可以用于解决大部分二分查找问题。在代码中，我们首先定义了两个变量 left 和 right，用来表示数组的左右边界。然后在 while 循环中不断缩小搜索区间，计算中间位置 mid，并将 mid 与目标值进行比较。如果 nums[mid] 等于目标值 target，那么说明已经找到目标值，直接返回 mid；如果 nums[mid] 小于目标值 target，那么说明目标值在右边，将 left 赋值为 mid + 1；如果 nums[mid] 大于目标值 target，那么说明目标值在左边，将 right 赋值为 mid - 1。直到 left 大于 right 时，说明已经搜索完整个区间，但是仍然没有找到目标值，此时返回 -1。

这个模板可以很好地适用于大多数二分查找问题，只需要在模板的基础上根据具体问题进行一些修改即可。需要注意的是，在使用二分查找时，数组必须是有序的。

# 二.二叉树

# 1.二叉树定义

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
        Copied!

1
2
3
4
5

# 2.二叉树的遍历

# 二叉树的遍历框架
def traverse(root: TreeNode):
    if not root:
        return

    # 前序遍历
    traverse(root.left)

    # 中序遍历

    traverse(root.right)

    # 后序遍历
 
        Copied!

1
2
3
4
5
6
7
8
9
10
11
12
13

# 3.二叉树的搜索框架

# 二叉树的搜索框架
def search(root: TreeNode, target: int) -> TreeNode:
    if not root or root.val == target:
        return root

    if target < root.val:
        return search(root.left, target)
    else:
        return search(root.right, target)
 
        Copied!

1
2
3
4
5
6
7
8
9

# 4.二叉树的插入框架

# 二叉树的插入框架
def insert(root: TreeNode, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)

    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)

    return root
 
        Copied!

1
2
3
4
5
6
7
8
9
10
11

02-算法总结 →