Binary Search

1. Code

1. 代码分析

1. 方法定义：
• public static int recursiveBinarySearch(int[] arr, int low, int high, int key)： 这是一个静态方法，接收四个参数：一个整数数组arr，两个表示搜索范围的整数low和high，以及要在数组中查找的键值key。

2. 递归终止条件：
• if (high < low)： 如果high小于low，表示搜索的范围无效，这时候将返回1，代表没有找到键值。

3. 计算中间索引：
• int mid = low + (high - low) / 2： 计算中间位置的索引mid，这样可以将数组分为两个部分进行查找。

4. 判断和递归搜索：
• if (key == arr[mid])： 如果中间位置的元素正好是要查找的键值，那么返回该位置的索引。
• else if (key < arr[mid])： 如果键值小于中间位置的元素，说明要查找的键值在左侧的子数组中，因此递归调用recursiveBinarySearch方法，将搜索范围修改为从low到mid - 1。
• else： 如果键值大于中间位置的元素，说明要查找的键值在右侧的子数组中，因此递归调用recursiveBinarySearch方法，将搜索范围修改为从mid + 1到high。

5. 主方法（main）的执行流程：
• 定义一个已排序的数组array和要查找的键值key。
• 调用recursiveBinarySearch方法进行查找。
• 根据返回的结果result，判断键值是否存在于数组中，并打印相应的消息。如果result等于1，打印“Element not present in the array”；否则，打印“Element found at index: ”加上找到的索引值。

Merge Sort

核心逻辑与实现

1. merge 方法：合并两个有序子数组

• 作用： 将数组 arr 的两个有序部分 [l..m] 和 [m+1..r] 合并为一个有序数组。

• 步骤：
1. 计算两个子数组的长度：n1 = m - l + 1 和 n2 = r - m。
2. 创建临时数组 L 和 R，分别存储左右两个子数组的数据。
3. 将 L 和 R 中的数据按顺序复制回原数组 arr。
4. 用两个指针 i 和 j 分别遍历临时数组 L 和 R，比较它们的值，将较小值复制到 arr[k]。
5. 如果一个子数组的数据已经全部复制完，则将另一个子数组的剩余数据直接复制到 arr。

2. sort 方法：递归地分割数组并排序

• 作用： 将数组 arr[l..r] 递归分割成小数组，排序后调用 merge 方法合并。

• 步骤：
1. 判断 l < r 是否成立（数组长度是否大于 1）。
2. 找到中间点 m = (l + r) / 2。
3. 递归调用 sort 方法对左半部分 arr[l..m] 和右半部分 arr[m+1..r] 进行排序。
4. 调用 merge 方法，将两个已排序的子数组合并。

3. printArray 方法：打印数组

• 作用： 遍历数组并打印其元素，用于显示排序前后数组的内容。

4. main 方法：程序入口

• 作用：
1. 定义一个待排序的数组。
2. 打印初始数组内容。
3. 调用 sort 方法对数组进行排序。
4. 打印排序后的数组。

程序运行逻辑

1. 输入：arr = {12, 11, 13, 5, 6, 7}

2. 分治过程：
• 第一次分割：{12, 11, 13} 和 {5, 6, 7}。
• 第二次分割：{12, 11} 和 {13}；{5, 6} 和 {7}。
• 第三次分割：{12} 和 {11}；{5} 和 {6}。

3. 合并过程：
• 合并 {12} 和 {11} 为 {11, 12}。
• 合并 {5} 和 {6} 为 {5, 6}。
• 合并 {11, 12} 和 {13} 为 {11, 12, 13}。
• 合并 {5, 6} 和 {7} 为 {5, 6, 7}。
• 合并 {11, 12, 13} 和 {5, 6, 7} 为 {5, 6, 7, 11, 12, 13}。

4. 输出：

归并排序的特点

1. 时间复杂度：
• 最佳情况、最坏情况和平均情况均为 。
O(nlog⁡n)O(n \log n)

2. 空间复杂度：
• 需要额外的存储空间来创建临时数组 和 ，因此空间复杂度为 。
LL
RR
O(n)O(n)

3. 稳定性：
• 归并排序是稳定的排序算法，因为相等元素在合并时不会交换顺序。

改进建议

1. 减少内存分配：
• 当前代码中每次合并时都重新创建临时数组 L 和 R，可以考虑复用数组来减少内存开销。

2. 非递归实现：
• 可以使用迭代方法（自底向上）来实现归并排序，避免递归带来的栈内存开销。