数据结构与算法 —— 常用算法模版

二分查找

人间若有天堂，大马士革必在其中；天堂若在天空，大马士革必与之齐名。 —— 阿拉伯谚语
算法若有排序，二分查找必在其中；排序若要使用，二分查找必与之齐名。 —— 木子李

（1）初始化左右指针
left 指向数组的起始位置（索引0）。
right 指向数组的末尾位置（索引len(arr) - 1）。
（2）循环条件
while left <= right：只要左指针不大于右指针，就继续搜索。这意味着搜索区间是有效的。
计算中间位置：
mid = left + (right - left) // 2：这是计算中间位置的标准方式。使用 (right - left) // 2 而不是 (right + left) // 2 是为了防止当 left 和 right 都很大时，它们的和可能超过整数类型的最大值，导致溢出。通过先减去再除以2，可以安全地计算出中间索引。
（3）检查中间元素
如果 arr[mid] == target，则找到了目标元素，返回其索引 mid。
如果 arr[mid] < target，说明目标元素在 mid 的右侧，因此将 left 更新为 mid + 1，缩小搜索范围到右半部分。
如果 arr[mid] > target，说明目标元素在 mid 的左侧，因此将 right 更新为 mid - 1，缩小搜索范围到左半部分。
（4）返回结果
如果循环结束还没有找到目标元素，则返回 -1，表示目标元素不在数组中。
（5）注意事项
确保输入的数组 arr 是有序的，因为二分查找依赖于数组的有序性。
mid 的计算方式可以防止整数溢出，这是在处理大数据集时的一个重要考虑因素。
返回值 -1 表示未找到目标元素，可根据需要自定义这个返回值。

# 排序是为了更快查找，不为了更快查找没必要排序。
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
    	# 防止(left + right)直接相加导致的整数溢出，这里mid有两种写法
        mid = left + (right - left) // 2  
        
        # 检查mid位置的元素
        if arr[mid] == target:
            return mid  # 找到目标，返回索引
        elif arr[mid] < target:
            left = mid + 1  # 目标在mid右侧
        else:
            right = mid - 1  # 目标在mid左侧
    
    return -1  # 未找到目标，返回-1

array = [1,2,3,4,5]
for left in range(0, len(array)):
	for right in range(left, len(array)):
	    
		if (right - left) % 2 == 0:
			print("奇数个元素:(",end="")
		else:
			print("偶数个元素:(",end="")
		for x in range(left, right + 1):
		    if x < right:
		        print(f"{x},",end="")
		    if x == right:
		        print(f"{x}",end="")
		print(")")
		# 关于mid的两种写法
		print(f"mid = (right + left) // 2 = ", (right + left) // 2)
		print(f"mid = (right + left + 1) // 2 = ", (right + left + 1) // 2)
		print("\n")

奇数个元素:(0)
(right + left) // 2 = 0
(right + left + 1) // 2 = 0

偶数个元素:(0,1)
(right + left) // 2 = 0
(right + left + 1) // 2 = 1

奇数个元素:(0,1,2)
(right + left) // 2 = 1
(right + left + 1) // 2 = 1
可以看到在偶数个元素时，(right + left) // 2 = mid下标偏左，(right + left + 1) // 2 = mid下标偏右，奇数个元素时都是对的

素数筛

def sieve_of_eratosthenes(n):
    # 创建一个布尔数组，初始化为 True，表示所有数都是素数
    is_prime = [True] * (n + 1)
    p = 2
    
    while (p * p <= n):
        # 如果 is_prime[p] 没有被改变，那么它是一个素数
        if is_prime[p]:
            # 更新 p 的所有倍数为 False，表示它们不是素数
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    
    # 收集所有的素数
    prime_numbers = [p for p in range(2, n + 1) if is_prime[p]]
    return prime_numbers

# 示例使用
n = 30
primes = sieve_of_eratosthenes(n)
print(f"小于或等于 {n} 的素数有: {primes}")

最大公约数与最小公倍数

# 最大公约数
"""
a = 40, b = 104
算法过程
a       b   remain
40  % 104 =   40 
104 %  40 =   24
40  %  24 =   16
24  %  16 =   8
16  %   8 =   0
8   %   0 =   不执行，结束
return a
"""
def gcd(a: int, b: int):
    while b != 0:
        remain = a % b
        a = b
        b = remain
    return a


# 最小公倍数
def lcm(a: int, b: int):
    return int((a * b) / gcd(a, b))


if __name__ == '__main__':
    print(gcd(400, 20))  # 20
    print(lcm(400, 20))  # 400