python算法：冒泡排序和二分查找

一、冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素并交换它们的位置，直到整个列表有序为止。这个过程就像气泡逐渐上升到表面一样，因此得名冒泡排序。

冒泡排序原理

1. 比较相邻元素：从列表的第一个元素开始，比较相邻的两个元素。
2. 交换位置：如果前一个元素大于后一个元素，则交换它们的位置。
3. 遍历列表：重复上述步骤，直到没有需要交换的元素为止。

冒泡排序示例

以下是一个使用Python实现的冒泡排序示例：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 标记是否发生交换
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # 交换元素
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 如果没有发生交换，说明列表已经有序，提前退出
        if not swapped:
            break
    return arr

# 示例列表
example_list = [64, 34, 25, 12, 22, 11, 90]

# 调用冒泡排序函数
sorted_list = bubble_sort(example_list)

print("排序后的列表:", sorted_list)

二、二分查找

二分查找（Binary Search）是一种高效的查找算法，适用于在有序数组中查找特定元素。它的基本思想是通过逐步缩小查找范围来快速定位目标元素。

二分查找原理

1. 初始化：确定查找范围的起始位置和结束位置，通常是数组的第一个元素和最后一个元素。
2. 计算中间位置：计算当前查找范围的中间位置。
3. 比较中间元素：将目标元素与中间位置的元素进行比较。
4. 如果目标元素等于中间元素，则查找成功，返回中间位置。
5. 如果目标元素小于中间元素，则将查找范围缩小到前半部分。
6. 如果目标元素大于中间元素，则将查找范围缩小到后半部分。
7. 重复步骤2和3：重复上述步骤，直到找到目标元素或查找范围为空。

二分查找示例

以下是一个使用Python实现的二分查找示例：

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # 如果未找到目标元素，返回-1

# 示例有序数组
example_array = [11, 12, 22, 25, 34, 64, 90]

# 目标元素
target_element = 22

# 调用二分查找函数
result = binary_search(example_array, target_element)

if result != -1:
    print(f"元素 {target_element} 在数组中的索引是 {result}")
else:
    print(f"元素 {target_element} 不在数组中")