### Python 实现折半查找和归并排序算法
#### 折半查找算法
**折半查找**（又称二分查找）是一种高效的查找方法，适用于已排序的数组或列表。其基本思想是在查找过程中逐步缩小查找范围，从而提高查找效率。
**算法步骤**：
1. **初始化**：设置查找范围的起始位置`low`和终止位置`high`，初始时`low = 0`，`high = n - 1`（n为数组长度）。
2. **中间值计算**：取中间位置`mid = (low + high) / 2`。
3. **比较与更新**：
- 如果目标值等于中间值，查找成功，返回该位置。
- 如果目标值小于中间值，则更新`high = mid - 1`，表示在左侧子数组中继续查找。
- 如果目标值大于中间值，则更新`low = mid + 1`，表示在右侧子数组中继续查找。
4. **循环执行**：重复步骤2和3，直到找到目标值或查找范围为空（即`low > high`），此时查找失败。
**Python 实现示例**：
```python
def bin_search(array, key, low, high):
if low > high:
return False # 查找失败
mid = int((low + high) / 2)
if key == array[mid]:
return mid # 查找成功
elif key < array[mid]:
return bin_search(array, key, low, mid - 1)
else:
return bin_search(array, key, mid + 1, high)
# 测试
array = [4, 13, 27, 38, 49, 49, 55, 65, 76, 97]
key = 76
result = bin_search(array, key, 0, len(array) - 1)
print(f"元素 {key} 的位置为: {result}")
```
**时间复杂度**：O(logn)，其中n为数组长度。
#### 归并排序算法
**归并排序**是一种基于分治策略的高效排序算法，其核心思想是将待排序的数据分成尽可能小的子集，然后将这些子集合并成最终的有序序列。
**算法步骤**：
1. **分解**：将数组分解成两部分，递归地进行相同的操作，直至每个子数组只有一个元素。
2. **合并**：将两个已排序的子数组合并成一个有序数组。
**Python 实现示例**：
```python
def merge_sort(array):
if len(array) <= 1:
return array
mid = int(len(array) / 2)
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
return merge(left, right)
def merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result.extend(left or right)
return result
# 测试
array = [49, 38, 65, 97, 76]
sorted_array = merge_sort(array)
print(sorted_array)
```
**时间复杂度**：O(nlogn)，无论最好、最坏还是平均情况下。
**空间复杂度**：O(n)，需要额外的空间用于合并操作。
**稳定性**：稳定排序算法，即相等的元素在排序后相对顺序不变。
### 小结
通过以上分析和示例代码，我们可以看到**折半查找**和**归并排序**这两种算法的实现原理及其Python实现方式。这两种算法都是计算机科学中的基础算法，掌握它们不仅有助于理解和解决实际问题，也是学习更高级算法的基础。
- 1
- 2
前往页