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

可视化网站链接：Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

Sorting is a very classic problem of reordering items (that can be compared, e.g., integers, floating-point numbers, strings, etc) of an array (or a list) in a certain order (increasing, non-decreasing (increasing or flat), decreasing, non-increasing (decreasing or flat), lexicographical, etc).There are many different sorting algorithms, each has its own advantages and limitations.Sorting is commonly used as the introductory problem in various Computer Science classes to showcase a range of algorithmic ideas.Without loss of generality, we assume that we will sort only Integers, not necessarily distinct, in non-decreasing order in this visualization. Try clicking Bubble Sort for a sample animation of sorting the list of 5 jumbled integers (with duplicate) above.

核心逻辑与实现

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