分治法与递归算法实验：二分查找、全排序和合并排序

一、实验目的

• 了解分治法思想；
• 掌握递归算法的思想与程序编写；
• 熟练使用二分查找法实现代码编写；
• 熟练使用全排序实现代码编写；
• 熟练使用合并排序实现代码编写；

二、实验内容

1. n个数的全排列问题。

2. 在一个给定的n个元素的有序序列中查找出与给定关键字x相同的元素的具体位置。即输入一个n个元素的序列，其中n个元素从小到大的顺序排列，查找是否存在给定的值x.(用二分查找法）。

3. 改写二分搜索算法：设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

4. 消除合并排序算法中的递归：给定数组a，将数组a中相邻元素两两配对，用合并算法将他们排序，构成n/2组长度为2的排好序的子数组段，然后再将它们排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。

三、实验总结

本次实验的收获包括：

1. 熟悉了分治法的思想，了解了它在算法设计中的应用，以及如何通过递归实现分治算法。

2. 掌握了递归算法的思想和编写方式，了解了递归的基本原理和递归调用的过程。

3. 熟练掌握了二分查找法的实现方式，了解了它在有序序列中查找特定元素的效率优势。

4. 熟悉了全排序和合并排序算法的实现方式，了解了它们在排序问题中的应用场景和算法效率。

在实验过程中，遇到了一些问题，例如在实现全排序和合并排序算法时，需要考虑到递归的边界条件和递归调用的方式，以避免出现死循环或错误的结果。此外，还需要注意算法的时间复杂度和空间复杂度，以确保算法的效率和可行性。

通过本次实验，我对分治法和递归算法有了更深入的理解，也提高了编写算法代码的能力。同时，我也意识到在实际应用中，选择合适的算法和数据结构对问题的解决具有重要的影响，需要根据具体情况进行选择和优化。