实验十二 实现顺序和二分查找算法[管理资料]

二分搜索算法实验报告篇一：实验报告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．掌握常见的排序算法（插入排序、交换排序、选择排序等）的思想、特点及其适用条件。

二分查找算法详解
一、算法介绍
二分查找算法又称折半查找算法，是一种分治思想的算法。

它的思想是：将空间定义为一个有序数组中从左到右的递增区间，每次进行二分查
找的时候，可以将空间缩小一半。

首先，取有序数组的中间元素作为比较
的对象，如果查找的目标元素与此元素相等，则直接输出结果；如果查找
的目标元素大于中间元素，则将查找范围减小一半，从中间元素的右半部
分继续进行查找；如果查找的目标元素小于中间元素，则将查找范围减小
一半，从中间元素的左半部分继续进行查找；如此反复，直到找到要查找
的目标元素，或者没有找到目标元素为止。

因此，如果要查找的元素在有
序数组中，二分查找算法有最佳的效率，因此，它是一种快速算法。

二、算法描述
1、首先，为有序数组定义low、high指针，令low指向有序数组的
第一个元素，high指向有序数组的最后一个元素。

2、然后，取有序数组的中间元素mid（即low和high的中间位置），将mid元素与查找的目标元素target进行比较。

3、如果target等于mid元素，则查找成功，输出mid元素的下标；
4、如果target大于mid元素，则将空间范围缩小一半，把low设置
为mid+1，继续进行二分查找；。

查找算法之二分查找算法二分查找算法（Binary Search）是一种在有序数组中快速查找目标值的算法。

它的基本思想是通过不断二分待查找区间，缩小查找范围，直到找到目标值或者确定目标值不存在。

二分查找算法的实现步骤如下：1. 确定待查找数组的起始位置 low 和结束位置 high，初始时 low = 0，high = 数组长度减12. 计算中间位置 mid，mid = (low + high) / 23.将目标值与中间位置的元素进行比较。

-如果目标值等于中间位置的元素，则找到目标值，返回中间位置。

- 如果目标值小于中间位置的元素，则目标值在数组的前半部分，更新 high = mid - 1，回到步骤2进行下一轮查找。

- 如果目标值大于中间位置的元素，则目标值在数组的后半部分，更新 low = mid + 1，回到步骤2进行下一轮查找。

4. 当 low 大于 high 时，代表目标值不存在于数组中，查找结束，返回 -1二分查找算法的时间复杂度为 O(log n)，其中 n 为数组长度。

由于每次查找都将查找范围缩小一半，所以它比线性查找算法的效率高很多。

除了基本的二分查找算法，还有一些变体的二分查找算法，如查找第一个与目标值相等的元素、查找最后一个与目标值相等的元素、查找第一个大于目标值的元素、查找最后一个小于目标值的元素等。

这些变体算法在算法思想上与基本的二分查找类似，只是在比较目标值与中间位置元素时稍微有所不同，并通过不同的条件更新 low 和 high 的值，从而实现不同的查找逻辑。

综上所述，二分查找算法是一种高效的查找算法，应用广泛且实用。

它的核心思想简单明了，通过将待查找区间逐渐缩小，快速定位目标值。

在实际应用中，我们需要根据具体问题场景选择恰当的二分查找算法，并注意一些特殊情况的处理，如数组为空、数组长度为0等。

实验十二实现顺序和二分查找算法实验十二：顺序和二分查找算法的实现一、引言在计算机科学中，查找是一种常见且重要的操作。

查找算法通过在数据集合中查找指定元素的位置，以及判断该元素是否存在，并返回相应的结果。

顺序查找和二分查找是两种常见的查找算法。

本实验将详细介绍并实现这两种算法。

二、顺序查找算法顺序查找算法，也称为线性查找算法，是一种简单直观的查找方法。

它逐个比较待查找的元素与数据集合中的每个元素，直到找到所需元素或遍历完整个数据集合。

以下是顺序查找算法的伪代码实现：1.初始化一个计数器i为0，用于记录当前查找的元素的索引位置。

2.从数据集合的第一个元素开始，逐个与待查找元素进行比较。

3.若找到所需元素，返回元素索引i。

4.若遍历完整个数据集合仍未找到所需元素，返回-1，表示未找到。

以下是使用Python编写的顺序查找算法的实现示例：```def sequential_search(arr, target):for i in range(len(arr)):if arr[i] == target:return ireturn -1```以上代码通过遍历列表中的每一个元素，逐个与目标元素进行比较，若找到则返回目标元素的索引，若未找到则返回-1、这是顺序查找算法的基本思想。

二分查找算法是一种高效的查找算法，也称为折半查找。

它要求待查找的数据集合必须有序排列。

算法的基本思想是通过将待查找区间反复划分为两半，然后确定目标元素存在的区间，最终找到所需元素或判断其不存在。

以下是二分查找算法的伪代码实现：1. 初始化一个左指针left指向数据集合的第一个元素，一个右指针right指向数据集合的最后一个元素。

2. 取中间位置middle，计算出该位置对应的元素mid_value。

3. 若mid_value等于目标元素target，则返回middle。

4. 若mid_value大于目标元素target，则将右指针right移动到middle-1的位置。

数据结构之⼆分法查找、快速排序思想与实现最近总是在想着，如何去设计，如何更好的编码，更充分地体会⾯向对象的思想，也刻意往这⽅⾯去学习。

写了⼏年代码，也改总结总结，发现最重要的还是在与思考。

重温了⼀下《程序设计实践》这本书，进⼀步规范反思下⾃⼰写的代码风格、质量、性能、可移植性等。

对了数据结构这⽅⾯的知识与算法进⼀步巩固。

下⾯写笔试经常遇见的算法：⼆分法查找、快速排序算法。

实现算法其关键在于实现的思想。

（⼀）⼆分法查找⼆分法查找其实就是折半查找，⼀种效率较⾼的查找⽅法。

针对有需数组来查找的。

主要思想是：（设查找的数组期间为array[low, high]）（1）确定该期间的中间位置K（2）将查找的值T与array[k]⽐较。

若相等，查找成功返回此位置；否则确定新的查找区域，继续⼆分查找。

区域确定如下：a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]b.array[k]<T 类似上⾯查找区间为array[k+1,……，high]。

每⼀次查找与中间值⽐较，可以确定是否查找成功，不成功当前查找区间缩⼩⼀半。

递归找，即可。

时间复杂度:O(log2n);代码实现:/// <summary>/// ⼆分法查找/// </summary>/// <param name="array">⽬标数组(已经排序好了)</param>/// <param name="a">查找的数</param>/// <returns>⽬标数的索引</returns>public int BinarySearch(int[] array, int T){int low, high, mid;low = 0;high = array.Length - 1;while (low <= high){mid = (low + high) / 2;if (array[mid] < T){low = mid + 1;}else if (array[mid]>T){high = mid - 1;}else{return mid;}}return -1;}（⼆）快速排序算法快速排序是尽量避免额外计算的极好例⼦.其⼯作⽅式是在数组中划分出⼩的和⼤的元素基本思想是：从数组中取出⼀个元素作为基准值把其他元素分为两组：“⼩的”是那些⼩于基准值的元素。

c语言数据结构实验报告二分查找二分查找是一种常用的查找算法，它可以在有序数组中快速定位目标元素的位置。

在本实验报告中，我们将详细介绍二分查找的原理和实现方法，并给出具体的示例代码。

一、原理介绍二分查找的原理很简单，它利用了有序数组的特性。

首先，将数组的中间元素与目标元素进行比较。

如果相等，则找到目标元素；如果目标元素小于中间元素，则在数组的左半部分继续查找；如果目标元素大于中间元素，则在数组的右半部分继续查找。

通过不断缩小查找范围，最终可以找到目标元素或确定目标元素不存在于数组中。

二、实现方法下面是使用C语言实现二分查找的示例代码：```c#include <stdio.h>int binarySearch(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;}if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}int main() {int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};int n = sizeof(arr) / sizeof(arr[0]);int target = 6;int index = binarySearch(arr, 0, n - 1, target);if (index != -1) {printf("目标元素在数组中的位置为：%d\n", index); } else {printf("目标元素不存在于数组中\n");}return 0;}```在上述代码中，`binarySearch`函数接收一个有序数组、数组的左右边界和目标元素作为参数。

二分搜索一．实验目的：1.理解算法设计的基本步骤及各步的主要内容、基本要求；2.加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题；3.通过本次实验初步掌握将算法转化为计算机上机程序的方法。

二．实验内容：1.编写实现算法：给定n个元素，在这n个元素中找到值为key的元素。

2.将输入的数据存储到指定的文本文件中，而输出数据存放到另一个文本文件中，包括结果和具体的运行时间。

3.对实验结果进行分析。

三．实验操作：1.二分搜索的思想：首先，假设表中的元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复上述过程，知道找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

由于二分搜索是基于有序序列的一种搜索算法，故将输入的一组数据首先进行排序，考虑到输入数据可能有多个，采用快速排或者是合并排序，其中与冒泡做了对比。

冒泡排序算法：void sort(int List[],int length){int change;for(int i=0;i<length;i++)for(int j=i+1;j<length;j++){if(List[i]>List[j]){change=List[i];List[i]=List[j];List[j]=change;}}}快速排序算法：void Qsort(int List[],int low,int high){if(low>=high) return;int first=low;int last=high;int key=List[first];while(first<last){while(first<last&&List[last]>=key) --last;List[first]=List[last];while(first<last&&List[first]<=key) ++first;List[last]=List[first];}List[first]=key;Qsort(List,low,first-1);Qsort(List,last+1,high);}二分查找算法：int binarySearch(int List[],int low,int high,int key){int mid=(low+high)/2;if(high<low) return -1;while(low<=high){if(List[mid]==key) return mid+1;else{if(List[mid]>key) return binarySearch(List,low,mid-1,key);else return binarySearch(List,mid+1,high,key);}}}2.实验数据的输入：本实验采用将数据输入与输出存储到文件中的方式，需要采用C++文件流操作，对于数据的输入，由于cin对数据的读取会忽略空格和换行操作，使用cin 流输入来控制数据的输入。

算法设计与分析各种查找算法的性能测试目录摘要 (2)第一章：简介（Introduction） (3)1.1 算法背景 (3)第二章：算法定义（Algorithm Specification） (4)2.1 数据结构 (4)2.2顺序查找法的伪代码 (4)2.3 二分查找（递归）法的伪代码 (5)2.4 二分查找（非递归）法的伪代码 (6)第三章：测试结果（Testing Results） (8)3.1 测试案例表 (8)3.2 散点图 (9)第四章：分析和讨论 (11)4.1 顺序查找 (11)4.1.1 基本原理 (11)4.2.2 时间复杂度分析 (11)4.2.3优缺点 (11)4.2.4该进的方法 (12)4.2 二分查找（递归与非递归） (12)4.2.1 基本原理 (12)4.2.2 时间复杂度分析 (13)4.2.3优缺点 (13)4.2.4 改进的方法 (13)附录：源代码（基于C语言的） (15)摘要在计算机许多应用领域中，查找操作都是十分重要的研究技术。

查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。

我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。

比较的指标为关键字的查找次数。

经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。

这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。

关键字：顺序查找、二分查找（递归与非递归）第一章：简介（Introduction）1.1 算法背景查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。

对于查找问题来说，没有一种算法在任何情况下是都是最优的。

有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。

【数据结构】查找算法：二分查找、顺序查找查找算法查找算法是在存在的序列（list）中查找特定的目标（target），要求序列中每个记录必须与一个关键词（key）关联才能进行查找。

查找算法通常需要两个输入：1、被查找的序列2、要查找的关键词查找算法的输出参数和返回值：1、返回类型为 Error_code 的值用以表示是否查找成功2、如果查找成功，返回success，输出参数position 定位到目标所在位置3、如果查找失败，返回 not present，输出参数可能是未定义或不同于已有位置的任何值顺序查找算法顺序查找算法的思路很简单：从表的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功；如果到最后一个元素仍没有目标元素，则查找失败。

【实验说明】题目：编写一个程序，对顺序表{3,6,2,10,1,8,5,7,4,9},采用顺序查找关键字5的过程。

要求输出：1）原顺序表；2）查找到关键字的位置；3）进行比较的次数。

1.首先要编写类表List。

需要满足最基本的操作插入insert（），获取retrieve（），以及得到大小size（）。

2.我们观察题目要求，表中虽然存储的是简单的整数，但如果我们使用List<int>对象显然无法记录比较次数，所以我们自己写一个类Key通过其内部int类型的数据成员来记录存于表中的值，并模仿int基本的逻辑操作，即编写重载逻辑运算符，同时增加一个静态数据成员comparisons用于记录其比较操作的次数。

3.准备工作做好之后开始编写顺序查找算法。

算法的思路很简单，也较易实现，从表中第一个元素开始比较，发现目标则返回元素所在表中位置；若遍历之后没有目标，则查找失败，返回-1表示表中没有目标元素。

4.按题目要求编写最后的输出函数。

【相关代码】函数 sequential_search[cpp]view plaincopy1.int sequential_search(const List<int> &the_list,2.const Key &target)3./*Post: If an entry in the_list is equal to target, thenreturn the position4. of this entry.5. Otherwise return -16.*/7.{8.int position;9.int s=the_list.size();10.for(position=0;position<s;position++){11.int data;12. the_list.retrieve(position,data);13.if(data==target){14.return position;15. }16. }17.return -1;18.}二分查找算法二分查找前提是表是按递增或递减顺序的规范表。