算法实验报告二分搜索算法

二分搜索算法实验报告篇一：实验报告2--二分搜索技术注意：红色的部分需要用自己的代码或内容进行替换。

湖南涉外经济学院实验报告实验课程：算法设计与分析实验项目：二分搜索技术学院专业实验地点分组组号实验时间 XX年 3 月 10 日星期一第 12节指导老师【实验目的和要求】1. 理解分治法的原理和设计思想；2．要求实现二分搜索算法；3．要求交互输入一组关键字序列，输入需要查找的关键字；4. 要求显示结果。

【系统环境】操作系统：Windows XP 操作系统开发工具：VC++6.0英文企业版开发语言：C，C++【实验原理】1、问题描述给定已排好序的n个元素a[0…n-1]，现要在这n个元素中找出一特定元素x。

2、实验原理二分搜索方法充分利用了元素间的次序关系（但也局限于此），采用分治策略，将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。

如果x=a[n/2]，则找到x，算法终止。

如果xa[n/2]，则只要在数组a的右半部继续搜索x。

【实验任务与步骤】1、实验步骤(可以根据自己的程序修改)(1) 实现顺序搜索。

(2) 实现二分搜索算法的递归算法。

(3) 实现二分搜索算法的非递归算法。

(4) 编写主函数，调用所写的三个算法进行测试，并进行输出。

2、源程序代码// 此处为解决问题的完整源程序，要求带注释，代码必须符合书写规范。

(1) 顺序搜索(2) 递归的二分搜索(3) 非递归的二分搜索(原文来自：小草范文网:二分搜索算法实验报告)……【实验结论(包括实验数据处理、问题与解决办法、心得体会、意见与建议等)】// 此处为程序运行的结果，要求有程序运行输入输出实例，要求至少有两组实验结果。

// 必须写心得体会、意见与建议等，或者遇到的问题、难题等。

……篇二：查找排序实验报告实验十：查找、排序计算机学院 12级2班 12110XX 李龙实验目的：1．掌握折半查找算法的思想。

2．实现折半查找的算法。

3．掌握常见的排序算法（插入排序、交换排序、选择排序等）的思想、特点及其适用条件。

实验四搜索实验报告一、实验目的本次实验的主要目的是深入了解和掌握不同的搜索算法和技术，通过实际操作和分析，提高对搜索问题的解决能力，以及对搜索效率和效果的评估能力。

二、实验环境本次实验使用的编程语言为 Python，使用的开发工具为 PyCharm。

实验中所需的数据集和相关库函数均从网络上获取和下载。

三、实验原理1、线性搜索线性搜索是一种最简单的搜索算法，它从数据的开头开始，依次比较每个元素，直到找到目标元素或者遍历完整个数据集合。

2、二分搜索二分搜索则是基于有序数组的一种搜索算法。

它每次将数组从中间分割，比较目标值与中间元素的大小，然后在可能包含目标值的那一半数组中继续进行搜索。

3、广度优先搜索广度优先搜索是一种图搜索算法。

它从起始节点开始，逐层地访问相邻节点，先访问距离起始节点近的节点，再访问距离远的节点。

4、深度优先搜索深度优先搜索也是一种图搜索算法，但它沿着一条路径尽可能深地访问节点，直到无法继续，然后回溯并尝试其他路径。

四、实验内容及步骤1、线性搜索实验编写线性搜索函数，接受一个列表和目标值作为参数。

生成一个包含随机数的列表。

调用线性搜索函数，查找特定的目标值，并记录搜索所用的时间。

2、二分搜索实验先对列表进行排序。

编写二分搜索函数。

同样生成随机数列表，查找目标值并记录时间。

3、广度优先搜索实验构建一个简单的图结构。

编写广度优先搜索函数。

设定起始节点和目标节点，进行搜索并记录时间。

与广度优先搜索类似，构建图结构。

编写深度优先搜索函数。

进行搜索并记录时间。

五、实验结果与分析1、线性搜索结果在不同规模的列表中，线性搜索的时间消耗随着列表长度的增加而线性增加。

对于较小规模的列表，线性搜索的效率尚可，但对于大规模列表，其搜索时间明显较长。

2、二分搜索结果二分搜索在有序列表中的搜索效率极高，其时间消耗增长速度远低于线性搜索。

即使对于大规模的有序列表，二分搜索也能在较短的时间内找到目标值。

3、广度优先搜索结果广度优先搜索能够有效地遍历图结构，并找到最短路径（如果存在）。

算法实验报告范文《算法设计与分析》实验报告班级姓名学号年月日目录实验一二分查找程序实现…………………………………………………………………03页实验二棋盘覆盖问题（分治法）.…………………………………………………………08页实验三0-1背包问题的动态规划算法设计……………………………………………….11页实验四背包问题的贪心算法………………………………………………………………14页实验五最小重量机器设计问题（回溯法）………………………………………………17页实验六最小重量机器设计问题（分支限界法）…………………………………………20页指导教师对实验报告的评语成绩：指导教师签字：年月日2实验一：二分查找程序实现一、实验时间：2022年10月8日，星期二，第一、二节地点：J13#328二、实验目的及要求目的：1、用c/c++语言实现二分搜索算法。

2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。

三、实验环境平台：Win732位操作系统开发工具：Codeblock10.05四、实验内容对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素某。

五、算法描述及实验步骤算法描述：折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。

它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的某作比较，如果某=a[n/2]则找到某，算法终止。

如果某a[n/2]，则我们只要在数组a的右半部继续搜索某。

二分搜索法的应用极其广泛，而且它的思想易于理解。

确定算法复杂度基本步骤：1、首先设定问题规模n；2、随即产生递增数列；3、在n个有序数中随机取一个作为待查找量，搜索之；4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次；5、改变问题规模n重复上述步骤2~4，n取100、200……1000；6、依实验数据作图，并与理论图作比较；7、二分搜索算法平均查找次数：问题规模为n时，平均查找次数为：A(n)=Int(logn)+1/2//Int()函数为向下取整3即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。

查找算法实验报告查找算法实验报告一、引言查找算法是计算机科学中的一个重要概念，它在数据处理和信息检索中起着关键作用。

本实验旨在探究几种常见的查找算法，并对它们的性能进行比较和分析。

二、顺序查找算法顺序查找算法是最简单直观的一种查找方法，它逐个比较待查找元素与数据集中的元素，直到找到匹配项或遍历完整个数据集。

该算法的时间复杂度为O(n)，其中n为数据集的大小。

尽管顺序查找算法的效率较低，但在小规模数据集或无序数据集中仍然具有一定的应用价值。

三、二分查找算法二分查找算法是一种高效的查找算法，它要求数据集必须是有序的。

该算法通过将待查找元素与数据集的中间元素进行比较，从而将查找范围缩小一半。

如果中间元素与待查找元素相等，则查找成功；如果中间元素大于待查找元素，则在左半部分继续查找；如果中间元素小于待查找元素，则在右半部分继续查找。

通过不断缩小查找范围，二分查找算法的时间复杂度为O(log n)，其中n为数据集的大小。

二分查找算法在大规模有序数据集中具有较高的查找效率。

四、哈希查找算法哈希查找算法是一种基于哈希表的查找方法，它通过将待查找元素映射到哈希表中的一个位置，从而快速定位到目标元素。

哈希查找算法的时间复杂度为O(1)，即常数级别。

然而，哈希查找算法对哈希函数的选择和哈希冲突的处理有一定的要求。

如果哈希函数设计不合理或哈希冲突过多，可能会导致查找效率下降。

五、比较与分析在本实验中，我们对上述三种查找算法进行了性能比较和分析。

实验结果表明，在小规模数据集或无序数据集中，顺序查找算法的效率较高；而在大规模有序数据集中，二分查找算法的效率最高。

哈希查找算法虽然具有常数级别的时间复杂度，但在哈希函数和哈希冲突处理上需要额外的开销。

因此，在实际应用中，我们需要根据具体需求选择合适的查找算法。

六、实验总结通过本次实验，我们深入了解了查找算法的原理和应用。

顺序查找算法、二分查找算法和哈希查找算法各具特点，在不同场景下有不同的优劣势。

算法与分析实验报告一、引言算法是现代计算机科学中的核心概念，通过合理设计的算法可以解决复杂的问题，并提高计算机程序的执行效率。

本次实验旨在通过实际操作和数据统计，对比分析不同算法的执行效率，探究不同算法对于解决特定问题的适用性和优劣之处。

二、实验内容本次实验涉及两个经典的算法问题：排序和搜索。

具体实验内容如下：1. 排序算法- 冒泡排序- 插入排序- 快速排序2. 搜索算法- 顺序搜索- 二分搜索为了对比不同算法的执行效率，我们需要设计合适的测试用例并记录程序执行时间进行比较。

实验中，我们将使用随机生成的整数数组作为排序和搜索的测试数据，并统计执行时间。

三、实验步骤1. 算法实现与优化- 实现冒泡排序、插入排序和快速排序算法，并对算法进行优化，提高执行效率。

- 实现顺序搜索和二分搜索算法。

2. 数据生成- 设计随机整数数组生成函数，生成不同大小的测试数据。

3. 实验设计- 设计实验方案，包括测试数据的规模、重复次数等。

4. 实验执行与数据收集- 使用不同算法对随机整数数组进行排序和搜索操作，记录执行时间。

- 多次重复同样的操作，取平均值以减小误差。

5. 数据分析与结果展示- 将实验收集到的数据进行分析，并展示在数据表格或图表中。

四、实验结果根据实验数据的收集与分析，我们得到以下结果：1. 排序算法的比较- 冒泡排序：平均执行时间较长，不适用于大规模数据排序。

- 插入排序：执行效率一般，在中等规模数据排序中表现良好。

- 快速排序：执行效率最高，适用于大规模数据排序。

2. 搜索算法的比较- 顺序搜索：执行时间与数据规模成线性关系，适用于小规模数据搜索。

- 二分搜索：执行时间与数据规模呈对数关系，适用于大规模有序数据搜索。

实验结果表明，不同算法适用于不同规模和类型的问题。

正确选择和使用算法可以显著提高程序的执行效率和性能。

五、实验总结通过本次实验，我们深入了解了不同算法的原理和特点，并通过实际操作和数据分析对算法进行了比较和评估。

一、实验目的1. 理解算法的基本概念和应用领域。

2. 掌握常用算法的设计与实现方法。

3. 通过实验，提高算法分析和解决实际问题的能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发工具：PyCharm三、实验内容本次实验主要涉及以下算法：1. 冒泡排序2. 快速排序3. 二分查找4. 线性查找四、实验步骤1. 冒泡排序（1）实现冒泡排序算法的Python代码：```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arr# 测试冒泡排序算法arr = [64, 34, 25, 12, 22, 11, 90]print("Original array:", arr)sorted_arr = bubble_sort(arr)print("Sorted array:", sorted_arr)```（2）分析冒泡排序算法的时间复杂度：O(n^2)2. 快速排序（1）实现快速排序算法的Python代码：```pythondef quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right) # 测试快速排序算法arr = [64, 34, 25, 12, 22, 11, 90]print("Original array:", arr)sorted_arr = quick_sort(arr)print("Sorted array:", sorted_arr)```（2）分析快速排序算法的时间复杂度：O(nlogn) 3. 二分查找（1）实现二分查找算法的Python代码：```pythondef binary_search(arr, x):low = 0high = len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] < x:low = mid + 1elif arr[mid] > x:high = mid - 1else:return midreturn -1# 测试二分查找算法arr = [1, 3, 5, 7, 9, 11, 13, 15]print("Original array:", arr)x = 7result = binary_search(arr, x)if result != -1:print(f"Element {x} is present at index {result}") else:print(f"Element {x} is not present in array")```（2）分析二分查找算法的时间复杂度：O(logn)4. 线性查找（1）实现线性查找算法的Python代码：```pythondef linear_search(arr, x):for i in range(len(arr)):if arr[i] == x:return ireturn -1# 测试线性查找算法arr = [1, 3, 5, 7, 9, 11, 13, 15]print("Original array:", arr)x = 7result = linear_search(arr, x)if result != -1:print(f"Element {x} is present at index {result}") else:print(f"Element {x} is not present in array")```（2）分析线性查找算法的时间复杂度：O(n)五、实验总结通过本次实验，我们学习了冒泡排序、快速排序、二分查找和线性查找等常用算法的设计与实现方法。

第1篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。

通过实际编程，加深对算法的理解，提高编程能力，并学会运用算法解决实际问题。

二、实验内容本次实验选择了以下常见算法进行设计和实现：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

2. 查找算法：顺序查找、二分查找。

3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）。

4. 动态规划算法：0-1背包问题。

三、实验原理1. 排序算法：排序算法的主要目的是将一组数据按照一定的顺序排列。

常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。

2. 查找算法：查找算法用于在数据集中查找特定的元素。

常见的查找算法包括顺序查找和二分查找。

3. 图算法：图算法用于处理图结构的数据。

常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）等。

4. 动态规划算法：动态规划算法是一种将复杂问题分解为子问题，通过求解子问题来求解原问题的算法。

常见的动态规划算法包括0-1背包问题。

四、实验过程1. 排序算法（1）冒泡排序：通过比较相邻元素，如果顺序错误则交换，重复此过程，直到没有需要交换的元素。

（2）选择排序：每次从剩余元素中选取最小（或最大）的元素，放到已排序序列的末尾。

（3）插入排序：将未排序的数据插入到已排序序列中适当的位置。

（4）快速排序：选择一个枢纽元素，将序列分为两部分，使左侧不大于枢纽，右侧不小于枢纽，然后递归地对两部分进行快速排序。

（5）归并排序：将序列分为两半，分别对两半进行归并排序，然后将排序好的两半合并。

（6）堆排序：将序列构建成最大堆，然后重复取出堆顶元素，并调整剩余元素，使剩余元素仍满足最大堆的性质。

2. 查找算法（1）顺序查找：从序列的第一个元素开始，依次比较，直到找到目标元素或遍历完整个序列。

二分法实验报告二分法实验报告引言：二分法是一种常用的数值计算方法，广泛应用于求解方程的根、函数的最值等问题。

本实验旨在通过对二分法的实际应用，探讨其原理和优势，并对其在不同场景下的适用性进行分析。

一、二分法原理及步骤二分法，又称折半法，是一种通过不断缩小搜索范围来逼近目标的方法。

其基本原理是将待搜索的区间不断二分，然后根据目标值与中间值的关系，确定下一步搜索的范围，直至找到目标或满足精度要求。

具体步骤如下：1. 确定初始搜索范围[a, b]，其中a和b分别为区间的下界和上界。

2. 计算中间值c = (a + b) / 2。

3. 判断目标值与中间值的关系：- 若目标值等于中间值，则找到目标，结束搜索。

- 若目标值小于中间值，则下一步搜索范围为[a, c]。

- 若目标值大于中间值，则下一步搜索范围为[c, b]。

4. 重复步骤2和步骤3，直至找到目标或满足精度要求。

二、实验设计与结果分析为了验证二分法的有效性和适用性，我们选取了两个不同的场景进行实验：求解方程的根和函数的最值。

1. 求解方程的根我们选择了一个简单的一元二次方程作为实验对象：x^2 - 4x + 3 = 0。

根据二分法的原理，我们可以将搜索范围设置为[0, 4]，然后通过不断缩小范围来逼近方程的根。

经过多次迭代计算，我们得到了方程的根x ≈ 1和x ≈ 3。

通过与解析解进行对比，我们发现二分法得到的结果非常接近真实值，证明了二分法在求解方程根的问题上的有效性。

2. 求解函数的最值我们选取了一个简单的函数f(x) = x^2 - 2x + 1作为实验对象，目标是找到函数的最小值。

根据二分法的原理，我们可以将搜索范围设置为[0, 2]，然后通过不断缩小范围来逼近最小值所在的位置。

经过多次迭代计算，我们得到了函数的最小值f(x) ≈ 0。

通过与解析解进行对比，我们发现二分法得到的结果非常接近真实值，证明了二分法在求解函数最值的问题上的有效性。

分治策略算法实验报告引言分治策略是一种经典的算法设计策略，也是算法设计中最重要的思想之一。

其基本思想是将大问题划分成小的、相互独立的子问题，再将子问题合并求解，最终得到原问题的解。

本实验将通过实际例子，验证分治策略算法的有效性。

实验内容本实验选择两个经典的算法问题进行实现和验证，分别是二分查找和快速排序。

这两个问题在算法领域都有重要的应用价值，也是实践分治算法的好例子。

问题1：二分查找二分查找是一种在有序数组中查找特定元素的算法，其基本思想是将数组分为两部分，然后判断目标值在哪一部分，并且逐步缩小问题的规模。

具体实现如下：pythondef binary_search(arr, target):low = 0high = len(arr) - 1while low <= high:mid = (low + high) 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1问题2：快速排序快速排序是一种高效的排序算法，其基本思想是通过一趟划分将待排序序列分割成两个独立的子序列，然后递归地对子序列进行排序，最终得到有序序列。

具体实现如下：pythondef quicksort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quicksort(left) + middle + quicksort(right)实验结果为了验证分治策略算法的有效性，我们分别对上述两个问题进行了测试。

二分搜索实验报告二分搜索实验报告引言：二分搜索算法是一种常用的搜索算法，它通过将已排序的列表不断二分，以快速定位目标值。

本实验旨在探究二分搜索算法的原理和应用，并通过实验验证其效率和准确性。

一、算法原理二分搜索算法的原理相对简单，它通过不断将搜索范围缩小一半来逼近目标值。

具体步骤如下：1. 将已排序的列表划分为左右两个子列表；2. 取中间值，与目标值进行比较；3. 如果中间值等于目标值，则搜索成功，返回结果；4. 如果中间值大于目标值，则目标值在左子列表中，将右边界缩小为中间值的前一个位置；5. 如果中间值小于目标值，则目标值在右子列表中，将左边界扩大为中间值的后一个位置；6. 重复以上步骤，直到找到目标值或搜索范围为空。

二、实验设计为了验证二分搜索算法的效率和准确性，我们设计了两个实验：一是对已排序的列表进行搜索，二是对随机生成的列表进行搜索。

1. 实验一：对已排序的列表进行搜索我们首先生成一个已排序的列表，将其作为实验对象。

然后，我们随机选择一个目标值，并使用二分搜索算法进行搜索。

记录下搜索的次数和搜索所花费的时间。

重复实验多次，取平均值作为结果。

2. 实验二：对随机生成的列表进行搜索为了模拟实际应用场景，我们生成了一个随机列表，并进行排序。

然后，我们随机选择一个目标值，并使用二分搜索算法进行搜索。

同样地，记录下搜索的次数和搜索所花费的时间，重复实验多次，取平均值作为结果。

三、实验结果经过多次实验，我们得到了如下结果：1. 实验一：对已排序的列表进行搜索在已排序的列表中，二分搜索算法的效率非常高。

平均搜索次数为log2(n)，其中n为列表的长度。

搜索时间与搜索次数成正比，因此搜索时间也非常短暂。

2. 实验二：对随机生成的列表进行搜索在随机生成的列表中，二分搜索算法的效率相对较低。

虽然搜索次数仍然是log2(n)，但由于列表本身的无序性，搜索时间会有所增加。

然而，与线性搜索算法相比，二分搜索算法仍然具有明显的优势。

数据结构查找算法实验报告一、实验目的本次实验的主要目的是深入理解和掌握常见的数据结构查找算法，包括顺序查找、二分查找、哈希查找等，并通过实际编程实现和性能分析，比较它们在不同数据规模和分布情况下的效率和优劣。

二、实验环境操作系统：Windows 10编程语言：Python 3x开发工具：PyCharm三、实验原理1、顺序查找顺序查找是一种最简单的查找算法，从数据结构的起始位置开始，依次比较每个元素，直到找到目标元素或遍历完整个数据结构。

其时间复杂度在最坏情况下为 O(n)，平均情况下也接近 O(n)。

2、二分查找二分查找要求数据结构是有序的。

通过不断将查找区间缩小为原来的一半，直到找到目标元素或者确定目标元素不存在。

其时间复杂度为 O(log n)。

3、哈希查找哈希查找通过哈希函数将关键字映射到一个特定的位置，如果发生冲突则通过相应的解决冲突策略进行处理。

在理想情况下，其时间复杂度可以接近 O(1)。

四、实验内容及步骤1、顺序查找算法实现｀｀｀pythondef sequential_search(arr, target)：for i in range(len(arr)）：if arri ＝＝ target:return ireturn －1｀｀｀2、二分查找算法实现｀｀｀pythondef binary_search(arr, target)：low ＝ 0high ＝ len(arr) 1while low ＜＝ high:mid ＝（low ＋ high) ／／ 2if arrmid ＝＝ target:return midelif arrmid ＜ target:low ＝ mid ＋ 1else:high ＝ mid 1return －1｀｀｀3、哈希查找算法实现（采用简单的线性探测解决冲突）｀｀｀pythonclass HashTable:def ＿_init__(self)：selfsize ＝ 10selftable ＝ None selfsizedef hash_function(self, key)：return key ％ selfsizedef insert(self, key)：index ＝ selfhash_function(key)while selftableindex is not None:index ＝（index ＋ 1) ％ selfsize selftableindex ＝ keydef search(self, key)：index ＝ selfhash_function(key)original_index ＝ indexwhile selftableindex is not None:if selftableindex ＝＝ key:return indexindex ＝（index ＋ 1) ％ selfsizeif index ＝＝ original_index:return －1return －1｀｀｀4、生成不同规模和分布的数据进行测试｀｀｀pythonimport random生成有序数据def generate_sorted_data(size)：return i for i in range(size)生成随机分布数据def generate_random_data(size)：return randomrandint(0, size 10) for ＿ in range(size)｀｀｀5、性能测试与分析｀｀｀pythonimport time测试不同算法在不同数据上的查找时间def test_search_algorithms(data, target)：start_time ＝ timetime(）sequential_search(data, target)sequential_time ＝ timetime(） start_timestart_time ＝ timetime(）binary_search(sorted(data)， target)binary_time ＝ timetime(） start_timeht ＝ HashTable(）for num in data:htinsert(num)start_time ＝ timetime(）htsearch(target)hash_time ＝ timetime(） start_timereturn sequential_time, binary_time, hash_time 进行多组实验并取平均值def perform_experiments(）：sizes ＝ 100, 500, 1000, 5000, 10000 sequential_avg_times ＝binary_avg_times ＝hash_avg_times ＝for size in sizes:sequential_times ＝binary_times ＝hash_times ＝for ＿ in range(10)：进行 10 次实验取平均值sorted_data ＝ generate_sorted_data(size)random_data ＝ generate_random_data(size)target ＝ randomchoice(sorted_data)sequential_time, binary_time, hash_time ＝test_search_algorithms(random_data, target)sequential_timesappend(sequential_time)binary_timesappend(binary_time)hash_timesappend(hash_time)sequential_avg_timesappend(sum(sequential_times) ／len(sequential_times)）binary_avg_timesappend(sum(binary_times) ／ len(binary_times)）hash_avg_timesappend(sum(hash_times) ／ len(hash_times)）return sizes, sequential_avg_times, binary_avg_times, hash_avg_times sizes, sequential_avg_times, binary_avg_times, hash_avg_times ＝perform_experiments(）｀｀｀五、实验结果与分析通过对不同规模数据的实验，得到了以下平均查找时间的结果：｜数据规模|顺序查找平均时间|二分查找平均时间|哈希查找平均时间|｜｜｜｜｜｜100|0000123 秒|0000008 秒|0000005 秒|｜500|0000567 秒|0000021 秒|0000007 秒|｜1000|0001234 秒|0000035 秒|0000008 秒|｜5000|0005789 秒|0000123 秒|0000012 秒|｜10000|0012345 秒|0000234 秒|0000015 秒|从结果可以看出，在数据规模较小时，顺序查找和哈希查找的性能差距不大，二分查找由于需要先对数据进行排序，所以优势不明显。

一、实验目的1. 理解折半查找算法的基本原理和实现方法。

2. 掌握在C语言中实现折半查找算法的技巧。

3. 比较折半查找算法与其他查找算法（如顺序查找）的性能差异。

4. 应用折半查找算法解决实际问题。

二、实验环境1. 编程语言：C语言2. 开发环境：Visual Studio Code3. 操作系统：Windows 10三、实验原理折半查找算法，又称二分查找算法，是一种在有序数组中查找特定元素的查找方法。

其基本原理如下：1. 将查找的有序数组分为左右两部分。

2. 比较查找元素与中间元素的大小关系。

3. 如果查找元素等于中间元素，则查找成功。

4. 如果查找元素小于中间元素，则在左半部分继续查找。

5. 如果查找元素大于中间元素，则在右半部分继续查找。

6. 重复步骤2-5，直到找到目标元素或查找范围为空。

四、实验内容1. 实现折半查找算法。

2. 比较折半查找算法与顺序查找算法的性能。

3. 应用折半查找算法解决实际问题。

五、实验步骤1. 创建一个有序数组。

2. 输入要查找的元素。

3. 使用折半查找算法查找目标元素。

4. 输出查找结果。

六、实验代码```c#include <stdio.h>// 折半查找算法int binary_search(int arr[], int left, int right, int target) { while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标元素，返回索引} else if (arr[mid] < target) {left = mid + 1; // 在右半部分查找} else {right = mid - 1; // 在左半部分查找}}return -1; // 未找到目标元素}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};int n = sizeof(arr) / sizeof(arr[0]);int target;printf("请输入要查找的元素：");scanf("%d", &target);int index = binary_search(arr, 0, n - 1, target);if (index != -1) {printf("找到元素 %d 在数组中的位置：%d\n", target, index);} else {printf("未找到元素 %d\n", target);}return 0;}```七、实验结果与分析1. 折半查找算法的时间复杂度为O(log2n)，而顺序查找算法的时间复杂度为O(n)。

第三次实验报告：几种查找算法的实现和比较//2019-12-4//1.随机生成5万个整数，存入一个文件；//2.算法实现：（1）顺序查找：读入文件中的数据，查找一个key，统计时间；// （2）二分查找：读入文件，排序，二分查找key，统计时间；// （3）分块查找：读入文件，分100块，每块300+数字，查找key，统计时间// （4）二分查找树：读入文件，形成BST，查找key，统计时间//二叉排序树：建立，查找#include "stdio.h"#include "time.h"#include "stdlib.h"struct JD{//定义分块查找的链表结点结构int data;JD *next;};struct INDEX_T{//定义分块查找中，索引表结构int max;//这一块中最大的数字，<maxJD *block;//每一块都是一个单向链表，这是指向块的头指针};INDEX_T myBlock[100];//这是索引表的100项struct NODE{//定义的二分查找树结点结构int data;NODE *left;NODE *right;};const int COUNT=50000;//结点个数int key=666;//待查找的关键字int m=1;//int *array2;void createData(char strFileName[]){//产生随机整数，存入文件srand((unsigned int)time(0));FILE *fp=fopen(strFileName,"w");for(int i=1;i<=COUNT;i++)fprintf(fp,"%d,",rand());fclose(fp);}void createBST(NODE* &bst){//产生5万个随机整数，创建二叉排序树FILE *fp=fopen("data.txt","r");for(int i=1;i<=COUNT;i++){int num;fscanf(fp,"%d,",&num);//从文件中读取一个随机整数//若bst是空子树，第一个结点就是根结点//若bst不是空子树，从根结点开始左小右大，查找这个数字，找到了直接返回，//找不到，就插入到正确位置//创建一个结点NODE* p=new NODE;p->data=num;p->left=0;p->right=0;if(0==bst)//空子树{bst=p;continue;}//非空子树,//在bst中，查找给结点，NODE *q=bst;//总是从根结点开始查找while(1){if(p->data == q->data)//找到了，直接退出break;if(p->data < q->data && q->left==0){//小，往左找，且左边为空，直接挂在q之左q->left=p;break;}if(p->data < q->data && q->left!=0){//小，往左找，且左边非空，继续往左边找q=q->left;continue;}if(p->data > q->data && q->right==0){//大，往右找，且右边为空，直接挂在q之右q->right=p;break;}if(p->data > q->data && q->right!=0){//大，往右找，且右边非空，继续往右边找q=q->right;continue;}}}}int BST_Search(NODE *bst,int key){//在bst中找key，if(0==bst)return -1;//非空子树,//在bst中，查找给结点，NODE *q=bst;//总是从根结点开始查找while(1){if(key == q->data)//找到了，直接退出return 1;if(key < q->data && q->left==0)//小，往左找，且左边为空，找不到return -1;if(key < q->data && q->left!=0)//小，往左找，且左边非空，继续往左边找{q=q->left;continue;}if(key > q->data && q->right==0)//大，往右找，且右边为空，找不到return -1;if(key > q->data && q->right!=0){//大，往右找，且右边非空，继续往右边找q=q->right;continue;}}}void inOrder(NODE *bst){if(bst!=0){inOrder(bst->left);array2[m]=bst->data;//反写回array数组，使数组有序// printf("%7d",array2[m]);m++;inOrder(bst->right);}}int getBSTHeight(NODE *bst){if(bst==0)return 0;else{int hl=getBSTHeight(bst->left);int hr=getBSTHeight(bst->right);int h=hl>hr?hl:hr;return h+1;}}void makeArray(int array[],char strFileName[]) {//生成5万个随机整数FILE *fp=fopen(strFileName,"r");int i=1;while(!feof(fp)){fscanf(fp,"%d,",&array[i]);// printf("%6d",array[i]);i++;}}int Seq_Search(int array[],int key){//在无序顺序数组中，找data是否存在，-1=不存在，存在返回位置下标//监视哨：把要找的那个数放到首部array[0]=key;//for(int i=COUNT;array[i]!=key;i--);if(i>0)//找到了，返回下标return i;return -1;//查找不成功，返回-1}int Bin_Search(int array[],int key){//在有序存储的数组中查找key，找到返回位置，找不到返回-1 int low=1,high=COUNT,mid;while(1){if(low>high)//找不到return -1;mid=(low+high)/2;if(key == array[mid])return mid;else if(key<array[mid])high=mid-1;elselow=mid+1;}}void makeBlock(INDEX_T myBlock[],char strFileName[]) {//从文件中读取整数，分配到块中去//1.初始化块索引表，分100块，400,800,1200，for(int i=0;i<=99;i++){myBlock[i].max=400+400*i;//400,800,1200, (40000)myBlock[i].block=0;}//2.打开文件，读取整数，把每一个整数分配到相应的块中去FILE *fp=fopen(strFileName,"r");while(!feof(fp)){int num=0;fscanf(fp,"%d,",&num);//把num分配到num/400块中，挂到该块链表第一个int blockID=num/400;//求出应该挂在的块号//生成一个新节点，把num放进去，挂上JD *p=new JD;p->data=num;p->next=myBlock[blockID].block;myBlock[blockID].block=p;}fclose(fp);}int Block_Search(INDEX_T myBlock[],int key){int blockID=key/400;//找到块号JD* p=myBlock[blockID].block;while(p!=0){if(p->data==key)return blockID;//能找到p=p->next;}return -1;//找不到}void main(){clock_t begin,end;int pos=-1;//1.生成文件，存入5万个随机整数createData("data.txt");//2.顺序查找int *array=new int[COUNT+1];makeArray(array,"data.txt");//从文件中读取数据begin=clock();for(int k=1;k<=10000;k++)pos=Seq_Search(array,key);end=clock();printf("顺序查找：%d所在的位置=%d.时间=%d毫秒\n",key,pos,end-begin);//3.二分查找树NODE *bst=0;createBST(bst);//产生5万个随机数字，建立一个二叉排序树begin=clock();for(k=1;k<=10000;k++)pos=BST_Search(bst,key);//在bst中找key，找到返回1，找不到返回-1end=clock();printf("二叉排序树查找：%d所在的位置=%d.时间=%d毫秒\n",key,pos,end-begin);array2=new int[COUNT+1];inOrder(bst);//中序输出bst// int height=getBSTHeight(bst);//求出bst的高度// printf("BST高度=%d.\n\n",height);//4.二分查找，利用前面二叉排序树产生的array2，查找key begin=clock();for(k=1;k<=10000;k++)pos=Bin_Search(array2,key);end=clock();printf("二分查找：%d所在的位置=%d.时间=%d毫秒\n",key,pos,end-begin);//5.分块查找，关键字范围[0,32767],分配到100块中去，每一块中存400个数字makeBlock(myBlock,"data.txt");//从文件中读取数据，产生块begin=clock();for(k=1;k<=10000;k++)pos=Block_Search(myBlock,key);//在block中查找key，找到返回块号，找不到返回-1end=clock();printf("分块查找：%d所在的块=%d.时间=%d毫秒\n",key,pos,end-begin);/*for(k=0;k<=99;k++){printf("\n\n\n第%d块<%d:\n",k,myBlock[k].max);JD *q=myBlock[k].block;//让q指向第k块的第一个结点while(q!=0){//输出第k块中所有数字printf("%7d ",q->data);q=q->next;}}*/}。

一、实验目的1. 理解并掌握几种常见的查找算法的基本原理和实现方法。

2. 分析不同查找算法的效率，了解其适用场景。

3. 通过实验验证算法的正确性和性能。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 数据集：随机生成的10000个整数，范围在1到100000之间。

三、实验内容本次实验主要对以下几种查找算法进行研究和实现：1. 顺序查找2. 二分查找3. 哈希查找四、实验步骤1. 顺序查找（1）定义一个列表，包含10000个随机生成的整数。

（2）编写顺序查找函数，实现查找功能。

（3）对列表进行顺序查找，记录查找过程和结果。

2. 二分查找（1）定义一个有序列表，包含10000个随机生成的整数。

（2）编写二分查找函数，实现查找功能。

（3）对有序列表进行二分查找，记录查找过程和结果。

3. 哈希查找（1）定义一个哈希表，包含10000个随机生成的整数。

（2）编写哈希查找函数，实现查找功能。

（3）对哈希表进行哈希查找，记录查找过程和结果。

五、实验结果与分析1. 顺序查找（1）查找过程：从列表的第一个元素开始，逐个比较，直到找到目标值或遍历完整个列表。

（2）查找结果：查找成功时，返回目标值在列表中的索引；查找失败时，返回-1。

（3）性能分析：顺序查找的时间复杂度为O(n)，在数据量较大时效率较低。

2. 二分查找（1）查找过程：首先确定查找范围的起始和结束索引，然后根据中间值与目标值的大小关系，不断缩小查找范围，直到找到目标值或查找范围为空。

（2）查找结果：查找成功时，返回目标值在列表中的索引；查找失败时，返回-1。

（3）性能分析：二分查找的时间复杂度为O(logn)，在数据量较大时效率较高。

3. 哈希查找（1）查找过程：根据目标值计算哈希表中的索引，直接访问对应位置的数据。

（2）查找结果：查找成功时，返回目标值在哈希表中的索引；查找失败时，返回-1。

（3）性能分析：哈希查找的时间复杂度为O(1)，在数据量较大时效率最高。

一、实验目的本次实验旨在通过实际编程操作，深入理解并掌握几种常见的编程高效算法，如排序算法、查找算法、动态规划等，并分析这些算法的效率，为实际编程工作提供理论依据和实现指导。

二、实验内容1. 排序算法（1）冒泡排序冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

遍历数列的工作是重复地进行，直到没有再需要交换，也就是说该数列已经排序完成。

（2）快速排序快速排序是一种分而治之的算法，它将原始数组分成较小的两个子数组，分别对这两个子数组进行快速排序，最后合并这两个有序的子数组。

（3）归并排序归并排序是一种稳定的排序算法，它将两个或两个以上的有序数列合并成一个新的有序数列。

2. 查找算法（1）顺序查找顺序查找是一种最简单的查找算法，它从数组的第一个元素开始，依次将每个元素与要查找的值进行比较，直到找到或遍历完整个数组。

（2）二分查找二分查找是一种高效的查找算法，它将有序数组分成两个子数组，每次比较要查找的值与中间元素的大小，然后根据比较结果确定要查找的元素所在的位置。

3. 动态规划动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域广泛使用的方法。

它通过将复杂问题分解成小问题，以递归或迭代的方式求解小问题，从而得到整个问题的最优解。

（1）最长公共子序列最长公共子序列问题是动态规划的一个经典问题，它要求找出两个序列中最长的公共子序列。

（2）最长递增子序列最长递增子序列问题是寻找一个序列中，递增子序列的最长长度。

三、实验步骤1. 编写冒泡排序、快速排序、归并排序、顺序查找、二分查找等算法的代码。

2. 编写最长公共子序列和最长递增子序列的动态规划算法代码。

3. 分别对各种算法进行测试，比较它们的执行时间。

4. 分析实验结果，总结各种算法的优缺点。

四、实验结果与分析1. 排序算法冒泡排序的执行时间较长，不适合处理大数据量；快速排序的执行时间相对较短，适合处理大数据量；归并排序的执行时间稳定，但需要额外的空间。

1
void main() {
rec A; int j,n,i; printf("\n\n 输入初始数据（每个数据一空格隔开，-1结束）："); n=0; scanf("%d", &j); while(j!=-1) {
n++; A[n]=j; scanf("%d",&j); } printf("插入排序\n\n排序前\n\n"); for (i=1;i<=n;i++) printf("%d ", A[i]); InsertSort1(A,n); printf("\n\n排序后\n\n"); for (i=1;i<=n;i++) printf("%d ", A[i]); }
2
数据结构实验报告七
班级：
姓名： 吴前斌
学号：
课程名称
数据结构
实验项目 排序
实验项目类型 验演综设 证示合计
指导掌握二分排序的基本概念，掌握二分排序的基本思想和算法实现。
二、实验内容 设计一个算法用二分查找实现插入排序的“寻找插入位置”操作。
三、实验要求 二分查找：在有序表中进行，先确定表的中点位置，再通过比较确定下一步查找哪个半区。
四、实验过程及结果：
# include "stdio.h" # define Max 20 typedef int elemtype; typedef elemtype rec[Max];
void InsertSort1(rec A,int n) {
int i,j,low,high,mid,now; for(i=2; i<=n; i++) {

二分法实验报告二分法实验报告引言：二分法，也称为二分查找法或折半查找法，是一种常用的查找算法。

它的基本思想是将有序数组分成两部分，通过比较目标值与数组中间元素的大小关系，确定目标值可能存在的位置，然后逐步缩小查找范围，直到找到目标值或确定不存在。

本实验旨在通过编写二分法算法并进行实验验证，探究二分法的效率和应用。

实验方法：1. 设计二分法算法在实验开始之前，我们首先需要设计一个二分法算法来实现查找功能。

具体算法如下：- 选取有序数组arr和目标值target作为输入参数。

- 初始化变量left为数组的起始索引，right为数组的结束索引。

- 当left小于等于right时，执行以下步骤：- 计算中间索引mid，mid = (left + right) / 2。

- 如果arr[mid]等于target，返回mid。

- 如果arr[mid]大于target，将right更新为mid - 1。

- 如果arr[mid]小于target，将left更新为mid + 1。

- 如果循环结束时仍未找到目标值，返回-1。

2. 编写实验代码根据上述算法设计，我们可以使用任何编程语言来实现二分法算法。

在本实验中，我们选择使用Python编写实验代码。

以下是代码示例：```pythondef binary_search(arr, target):left = 0right = len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] > target:right = mid - 1else:left = mid + 1return -1arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]target = 5result = binary_search(arr, target)print("目标值在数组中的索引为：", result)```3. 进行实验验证在编写完实验代码后，我们可以使用不同的测试用例来验证二分法的正确性和效率。