数据结构实验报告---折半查找

有序表的折半查找算法一、前言有序表是一种常用的数据结构，它可以使查找、插入和删除等操作更加高效。

而折半查找算法是一种常用的查找有序表中元素的方法，它可以在较短的时间内定位到目标元素。

本文将详细介绍有序表的折半查找算法。

二、有序表有序表是一种按照某个关键字排序的数据结构，其中每个元素都包含一个关键字和相应的值。

有序表的排序方式可以是升序或降序，而且排序依据可以是任何属性。

例如，在一个学生信息系统中，可以按照学号、姓名、年龄等属性对学生信息进行排序。

由于有序表已经按照某个关键字排序，因此在进行查找、插入和删除等操作时，可以采用更加高效的算法。

其中最常见的算法之一就是折半查找算法。

三、折半查找算法1. 基本思想折半查找算法也称为二分查找算法，其基本思想是：将待查元素与有序表中间位置上的元素进行比较，如果相等，则返回该位置；如果待查元素小于中间位置上的元素，则在左半部分继续进行二分查找；否则，在右半部分继续进行二分查找。

重复以上过程，直到找到目标元素或确定其不存在为止。

2. 算法实现折半查找算法的实现可以采用递归或循环方式。

以下是采用循环方式实现的伪代码：```int binarySearch(int[] a, int target) {int left = 0;int right = a.length - 1;while (left <= right) {int mid = (left + right) / 2;if (a[mid] == target) {return mid;} else if (a[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1; // 没有找到目标元素}```在以上代码中，`a` 表示有序表，`target` 表示待查元素。

首先，将左右指针 `left` 和 `right` 分别初始化为有序表的第一个和最后一个元素的下标。

1. 理解折半查找法的基本原理和适用条件。

2. 掌握折半查找法的实现方法。

3. 通过实验验证折半查找法的效率。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验内容1. 实现折半查找法。

2. 对折半查找法进行测试，包括：a. 对已排序的数组进行查找；b. 对未排序的数组进行查找；c. 查找不存在的元素。

四、实验步骤1. 定义一个整型数组，并对其进行排序。

2. 实现折半查找函数，包括：a. 定义折半查找函数的参数，包括数组、目标值和数组的长度；b. 实现折半查找算法；c. 返回查找结果，包括找到的位置和未找到。

3. 对已排序的数组进行查找，输出查找结果。

4. 对未排序的数组进行查找，输出查找结果。

5. 对不存在的元素进行查找，输出查找结果。

```cpp#include <iostream>#include <algorithm>// 折半查找函数int binarySearch(const int arr, int target, int left, int right) { 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 = 11; // 目标值// 对数组进行排序std::sort(arr, arr + n);// 对已排序的数组进行查找int index = binarySearch(arr, target, 0, n - 1);if (index != -1) {std::cout << "已排序数组中找到目标值：" << target << "，位置为：" << index << std::endl;} else {std::cout << "已排序数组中未找到目标值：" << target << std::endl;}// 对未排序的数组进行查找int unsortedArr[] = {9, 5, 3, 7, 1, 11, 13, 17, 15, 19};int unsortedIndex = binarySearch(unsortedArr, target, 0, n - 1);if (unsortedIndex != -1) {std::cout << "未排序数组中找到目标值：" << target << "，位置为：" << unsortedIndex << std::endl;} else {std::cout << "未排序数组中未找到目标值：" << target << std::endl;}// 对不存在的元素进行查找int notExistTarget = 20;int notExistIndex = binarySearch(arr, notExistTarget, 0, n - 1);if (notExistIndex != -1) {std::cout << "数组中找到目标值：" << notExistTarget << "，位置为：" << notExistIndex << std::endl;} else {std::cout << "数组中未找到目标值：" << notExistTarget <<std::endl;}return 0;}```六、实验结果与分析1. 对已排序的数组进行查找，折半查找法成功找到了目标值，查找效率较高。

折半查找法c语言折半查找法，又称二分查找法，是一种在有序数据集（顺序表/列表、数组等）中，快速查找指定值的高效算法。

折半查找法的思想是基于二分法思想，用“分而治之”的思想来快速查找指定值。

折半查找法是一种最常用的查找方法，它也被称为是一种“有序”查找，因为要查找的数据必须是已经排好序的。

实际上，折半查找法的实现只要将有序的数据列折半，一次比较即可将待查找的值与被折半的数据列比较，这样查找的过程会比较快捷。

下面就来介绍折半查找法的具体实现方式：折半查找法假设要查找的数据是一个有序数列，在这里以升序数列为例：（1）先定义一个指向待查找序列低位的索引，称之为low；（2）定义另一个指向待查找序列高位的索引，称之为high；（3）首先用low与high计算中位索引 mid，将这个中位索引处的值与要查找的数据进行比较，如果相等，则搜索成功；（4）如果不等，则根据要查找的数据与中位索引处的值的比较结果，将待查找的序列分为两部分，下次查找只要在其中一部分序列中继续进行折半查找即可。

有了上面的思路，我们就可以用c语言来实现折半查找法了。

代码如下：#include<stdio.h>int binary_search(int arr[], int n, int key){int low, mid, high;low = 0;high = n-1;while(low <= high){mid = (low + high) / 2;if(arr[mid] == key)return mid;else if(arr[mid] > key)high = mid - 1;elselow = mid + 1;}return -1;}int main(){int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int res = binary_search(arr, 10, 7);printf(res = %d res);return 0;}以上就是一个最基本的折半查找法的实现，通过定义一个low、high和mid三个索引，在计算中位索引mid时，low和high 分别指向有序数列的低位和高位，根据判断条件，如果要查找的值等于中位索引处的数据，则查找成功，否则就用待查找的数据与中位索引处的数据进行比较，来确定下一次查找的范围。

折半查找判定树的特点
折半查找（Binary Search）判定树是一种用于分析二分查找算法的数据结构。

以下是折半查找判定树的一些特点：
1.平衡性：折半查找判定树是一棵平衡二叉树。

在最坏情况下，每一层的节点数量都接近于对数的底数为2，这保证了查找的效率。

2.查找时间复杂度：对于包含n个元素的有序数组，折半查找的时间复杂度为O(log n)。

这是因为每一次比较都会将搜索范围缩小一半。

3.插入和删除的复杂度：插入和删除操作不如查找高效。

由于需要保持有序性，插入和删除的平均时间复杂度为O(log n)，但在最坏情况下可能需要O(n)的时间来调整平衡。

4.节点结构：每个节点表示一个比较操作，包含有关元素和比较值的信息。

树的叶子节点表示查找成功的结束点，而非叶子节点表示查找的比较过程。

5.路径长度：对于n个元素的有序数组，折半查找判定树的路径长度为log₂(n)+1。

路径长度是指从根节点到达叶子节点的最短路径的长度。

6.对数性质：折半查找的效率主要依赖于对数的性质。

每一次比较都将搜索范围缩小一半，因此查找的时间复杂度是对数级别的。

7.适用性：折半查找适用于有序数组，因为它依赖于元素的有序性。

如果数据经常需要进行查找而不是插入和删除，折半查找是一种高效的算法。

总的来说，折半查找判定树是一种用于分析二分查找算法行为的有用工具，它展示了查找过程中关键比较的次数和顺序。

一、实验目的熟练掌握顺序查找，折半查找和哈希表等算法的程序实现。

二、实验内容1、实现折半查找的算法编写一个程序，输出在顺序表（1,2,3,4,,6,7,8,9,10）中采用折半查找方法查找关键字9的过程要求：输出查找过程中的比较对象和被查找元素的位置。

2、实现哈希表的相关运算算法编写程序实现哈希表的构造过程。

要求：建立关键字序列（16,74,60,43,54,90,46,31,29,88,77）对应的哈希表A[0...12]，哈希函数为H（k）=k%p，并采用开放定址法中的线性探测法解决冲突。

输出构造完成后的哈希表。

程序源代码及运行结果（运行结果可以截图，也可以文字描述分析）1#include<stdio.h>#include<stdlib.h>int fun(int a[],int key){int high=9;int low=0;int mid=(high+low)/2;printf("与之相比较的值为:");while(high>=low){if(key==a[mid]){printf("%-2d",a[mid]);printf("\nkey为数组中第%d个元素\n",mid+1);break;}if(key<a[mid]){ printf("%-2d",a[mid]);high=mid-1;mid=(high+low)/2;}if(key>a[mid]){ printf("%-2d",a[mid]);low=mid+1;mid=(high+low)/2;}}}int main(){int a[10]={1,2,3,4,5,6,7,8,9,10};fun(a,9);system("pause");}运行截图：2#include<stdio.h>int main(){int a[11]={16,74,60,43,54,90,46,31,29,88,77};int A[13]={0};int p=11,H;for(int i=0;i<11;i++){H=a[i]%p;while(A[H]!=0){H++;if(H==12){H=0;}}A[H]=a[i];}for(int i=0;i<13;i++){if(A[i]!=0){printf("%d ",A[i]);}}}运行截图三、小结（不少于100字）感觉好像没有真正理解哈希表，折半查找比较好理解，实现起来也比较容易，自己对代码的熟练程度还不够，课后还会多多练习，查找的方式还有很多，课后应该多看书，对每种算法都有一定的了解。

实验五查找的应用一、实验目的：1、掌握各种查找方法及适用场合，并能在解决实际问题时灵活应用。

2、增强上机编程调试能力。

二、问题描述1.分别利用顺序查找和折半查找方法完成查找。

有序表（3,4,5,7,24,30,42,54,63,72,87,95）输入示例：请输入查找元素：52输出示例：顺序查找：第一次比较元素95第二次比较元素87 ……..查找成功，i=**/查找失败折半查找：第一次比较元素30第二次比较元素63 …..2.利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序树，并完成指定元素的查询。

输入输出示例同题1的要求。

三、数据结构设计（选用的数据逻辑结构和存储结构实现形式说明）（1）逻辑结构设计顺序查找和折半查找采用线性表的结构，二叉排序树的查找则是建立一棵二叉树，采用的非线性逻辑结构。

（2）存储结构设计采用顺序存储的结构，开辟一块空间用于存放元素。

（3）存储结构形式说明分别建立查找关键字，顺序表数据和二叉树数据的结构体进行存储数据四、算法设计（1）算法列表（说明各个函数的名称，作用，完成什么操作）序号 名称 函数表示符 操作说明1 顺序查找 Search_Seq 在顺序表中顺序查找关键字的数据元素2 折半查找 Search_Bin 在顺序表中折半查找关键字的数据元素3 初始化 Init 对顺序表进行初始化，并输入元素4 树初始化 CreateBST 创建一棵二叉排序树5 插入 InsertBST 将输入元素插入到二叉排序树中6 查找 SearchBST在根指针所指二叉排序树中递归查找关键字数据元素 （2）各函数间调用关系（画出函数之间调用关系）typedef struct { ElemType *R; int length;}SSTable;typedef struct BSTNode{Elem data; //结点数据域 BSTNode *lchild,*rchild; //左右孩子指针}BSTNode,*BSTree; typedef struct Elem{ int key; }Elem;typedef struct {int key;//关键字域}ElemType;（3）算法描述int Search_Seq(SSTable ST, int key){//在顺序表ST中顺序查找其关键字等于key的数据元素。

折半查找和二叉排序树一、实验目的1、掌握查找的特点。

2、掌握折半查找的基本思想及其算法。

3、熟悉二叉排序树的特点，掌握二叉排序树的插入、删除操作。

二、实验内容1、设有关键字序列k={ 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35 }，查找key=21和key=25的数据元素。

2、根据关键字序列{45、24、53、12、37、93}构造二叉排序树，并完成插入13删除关键字53和24的操作。

三、实验环境TC或VC++或Java四、实验步骤1、折半查找（1）从键盘输入上述8个整数5 ,14 ,18 ,21 ,23 ,29 ,31 ,35，存放在数组bub[8]中，并输出其值。

（2）从键盘输入21，查找是否存在该数据元素，若存在，则输出该数据元素在表中的位置，否则给出查找失败的信息。

（3）从键盘输入25，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。

2、二叉排序树（1）二叉排序树存储定义（2）从键盘上输入六个整数45、24、53、12、37、9构造二叉排序树（3）输出其中序遍历结果。

（4）插入数据元素13，输出其中序遍历结果。

（5）删除数据元素24和53，输出其中序遍历结果。

五、问题讨论1、折半查找递归算法该怎么描述？2、二叉排序树中序遍历结果有什么特点？3、在二叉树排序树中插入一个新结点，总是插入到叶结点下面吗？4、在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同吗？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题回答7、实验心得实验代码：#include<stdio.h>#include<stdlib.h>typedef struct BiTNode{int data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;int bub[100];void menu(){printf("********主目录*******\n");printf(" 折半或顺序查找1\n");printf(" 二叉排序树2\n");printf(" 结束程序0\n");printf("*********************\n");}void menu1(){printf("*******目录①*******\n");printf(" 输出元素1\n");printf(" 顺序查找2\n");printf(" 折半查找3\n");printf(" 结束此查找0\n");printf("********************\n");}void menu2(){printf("**********目录②*********\n");printf("输出树的中序遍历结果1\n");printf(" 插入数据元素2\n");printf(" 删除数据元素3\n");printf(" 结束二叉排序0\n");printf("*************************\n"); }void Search(){int i,m,n,key,k;printf("输入元素个数：");scanf("%d",&m);printf("依次输入元素：");for(i=1;i<=m;i++){scanf("%d",&bub[i]);}printf("输入关键字：");scanf("%d",&key);bub[0] = key;do{menu1();printf("选择查找方式：");scanf("%d",&n);switch(n){case 1:for(i=1;i<=m;i++){printf("%d,",bub[i]);}printf("\n");break;case 2:for(i=m;i>=0;i--){if(bub[i]==key){if(i!=0){printf("查找的数据元素在第%d位！\n",i);break;}else{printf("查找失败\n");}}}break;case 3:k = Search_Bin(m,key);if(k!=0)printf("查找的数据元素在第%d位！\n",k);elseprintf("查找失败\n");break;case 0:printf("查找结束\n");break;default:printf("选择错误\n");}}while(n!=0);}int Search_Bin(int m,int key){int low,high,mid;low = 1;high = m;while(low<=high){mid = (low+high)/2;if(key==bub[mid])return mid;else if(key<bub[mid])high = mid-1;elselow = mid+1;}return 0;}BiTree Insert(){BiTree T=NULL,q=NULL,p=NULL;int m;printf("输入数据(-10000停止输入)：");scanf("%d",&m);while(m!=-10000){q = (BiTree)malloc(sizeof(BiTNode));q->data = m;q->lchild = q->rchild=NULL;if(!T)T = q;else{p = T;while(1){if(m<p->data){if(p->lchild==NULL){p->lchild = q;break;}p = p->lchild;}else{if(p->rchild==NULL){p->rchild = q;break;}p = p->rchild;}}}scanf("%d",&m);}return T;}void Inorder(BiTree T){if(T){Inorder(T->lchild);printf("%d,",T->data);Inorder(T->rchild);}}int Search_CH(BiTree T,int elem,BiTree f,BiTree *p) {if(!T){*p = f;return 0;}else if(elem==T->data){*p = T;return 1;}else if(elem<T->data)Search_CH(T->lchild,elem,T,p);elseSearch_CH(T->rchild,elem,T,p);}BiTree InsertBST(BiTree T,int elem){BiTree p=NULL,s=NULL;if(!Search_CH(T,elem,NULL,&p)){s = (BiTree)malloc(sizeof(BiTNode));s->data = elem;s->lchild = s->rchild = NULL;if(!p)T = s;else if(elem<p->data)p->lchild = s;elsep->rchild = s;printf("插入成功\n");return T;}printf("输入已有元素，插入失败\n");return T;}BiTree Delete(BiTree T,int elem){BiTree p=NULL,q=NULL,f=NULL,s=NULL;p = T;while(p){if(elem == p->data)break;q = p;if(elem <p->data)p = p->lchild;elsep = p->rchild;}if(!p)printf("查找失败，删除失败\n");return T;}if(!(p->lchild)){if(!q)T = p->rchild;else if(q->lchild == p)q->lchild = p->rchild;elseq->rchild = p->rchild;free(p);}else{f = p;s = p->lchild;while(s->rchild){f = s;s = s->rchild;}if(f==p)f->lchild = s->lchild;elsef->rchild = s->lchild;p->data = s->data;free(s);}printf("删除成功\n");return T;}void ErChaPaiXu(){BiTree T;int m,key;T = Insert();domenu2();printf("输入你的选择：");scanf("%d",&m);switch(m){case 1:printf("中序遍历结果为：");Inorder(T);printf("\n");break;case 2:printf("输入要插入的元素：");scanf("%d",&key);T = InsertBST(T,key);break;case 3:printf("输入要删除的元素：");scanf("%d",&key);T = Delete(T,key);break;case 0:printf("结束二叉排序\n");break;default:printf("输入错误\n");}}while(m!=0);}void main(){int m;do{menu();printf("输入你的选择：");scanf("%d",&m);switch(m){case 1:Search();break;case 2:ErChaPaiXu();break;case 0:printf("程序已结束\n");break;default:printf("输入错误\n");}}while(m!=0);}。

实验五查找得实现一、实验内容1、建立一个线性表,对表中数据元素存放得先后次序没有任何要求.输入待查数据元素得关键字进行查找。

为了简化算法,数据元素只含一个整型关键字字段,数据元素得其余数据部分忽略不考虑.建议采用前哨得作用，以提高查找效率。

2、查找表得存储结构为有序表,输入待查数据元素得关键字利用折半查找方法进行查找.此程序中要求对整型量关键字数据得输入按从小到大排序输入。

二、源代码与执行结果1、＃inclｕｄｅ〈ｉoｓtreａm>ｕsiｎg namespace stｄ；＃defｉne MAX １０0＃deｆinｅ KｅyTｙpe iｎｔtypｅｄef stｒuct{ＫｅｙＴｙpe key ；｝DataTｙpe；typedef struｃt{ﻩDaｔaＴyｐｅ elem[ＭAX］ ;iｎｔlength ；}SeqTａble ，＊PSeｑTable ；PSeｑTable Ｉniｔ_SｅqＴable（){ﻩＰSｅqTable p ＝（ＰＳｅｑTable）malｌoc(ｓizeof（SeｑTable)) ;ﻩiｆ（p ！＝ＮULＬ）｛p->lｅｎgtｈ = 0 ；ﻩｒｅｔｕrnｐ；}ﻩelsｅ｛ﻩｃｏｕt〈<"Ouｔｏf space!”〈〈endl ；ﻩrｅtuｒn NＵＬL;ﻩ}｝int insert＿SeqTable（PSeｑTable p,KeｙType x){ｉｆ(ｐ-＞length〉= ＭＡX）ﻩ｛ﻩcｏｕt〈<”ｏverｆｌow！"<<endl ;ﻩreｔuｒn 0 ；ﻩ}ｐ—>ｅlem[ｐ—＞leｎgｔh］、key＝ x ;p-〉ｌｅｎｇtｈ+＋；reｔurｎ 1 ;｝iｎｔ SｅqSｅarch（SｅqTａble s ,KｅｙTypｅk){ﻩｉnt n ， i = ０；ﻩn = s、ｌength ；s、eleｍ［n］、ｋeｙ =ｋ ;ﻩwhilｅ（s、eｌem[i］、key ！= k）ﻩﻩi ＋+ ;ﻩif(i == n）retｕrn —1 ；elseﻩﻩrｅturn i ;}ｖoidｍain（）｛PSeｑTabｌe ｐ ;intｉ , ｎ；ﻩKeyＴype a ;p =Ｉnit_ＳｅqTaｂｌｅ（）；ﻩｃout<〈"请输入数据个数：" ;ｃin＞>n ；couｔ〈＜＂请输入数据：”＜〈endｌ ;fｏr(ｉ = 0 ; ｉ＜ n ;ｉ＋+）ﻩ{ﻩciｎ〉＞a ；ﻩinsert_SｅqTaｂle（p , a）；｝ﻩcｏut＜＜"请输入要查找得数据，输入3２76７结束：” ；cin〉〉ａ ;ﻩwｈiｌｅ（a ！= ３27６７)ﻩ｛i =SｅｑSearcｈ(*p， a) ；ｉf（i == -１）{ﻩﻩﻩcｏｕt＜＜”无此数据!请重新输入：＂<〈ｅｎｄl ；ﻩﻩcin＞＞a ；ﻩ｝ﻩﻩeｌｓeﻩﻩ｛ﻩcout＜〈"该数据得位置就是：＂〈<i+1<<enｄｌ；ﻩcouｔ〈＜＂请输入要查找得数据：" ；ﻩﻩｃiｎ〉〉ａ；ﻩ}ﻩ｝｝2、＃incｌｕde<iosｔream>usinｇ naｍespace stｄ；#defｉne MAX 100＃dｅfine KeyTyｐe ｉｎtｔyｐedef sｔruct{KeyTｙpe key ；｝ＤataTypｅ；typedeｆ stｒuｃt｛ﻩDataType ｅｌem［MAX] ；ﻩinｔ length ；}BinTａbｌe ,＊PBｉnＴabｌe ;PBinTabｌｅ Iniｔ_BiｎTablｅ（）｛ﻩPBinＴable p = (PBiｎTabｌe)mａlloｃ（sizeof(ＢinTable）) ;if(p ！= ＮULＬ)｛p->length= ０；ﻩﻩｒeturn p ；ﻩ}eｌseﻩ{ﻩｃout〈<＂Ｏｕt ｏｆ spａｃe！"〈＜endl ;rｅturｎ NUＬL ;ﻩ｝｝int iｎsｅｒt＿BinTａble（PBinTａble p ，ＫｅyTｙpe x）{ｉf（p—〉ｌｅnｇth ＞＝ MAX)｛ﻩｃoｕt<＜"ｏｖerflow!”<〈ｅnｄl ;ﻩreturn 0 ;ﻩ}ﻩp－〉ｅlｅm［p—＞lｅngtｈ］、key =x ;ｐ->ｌengtｈ ++ ；ﻩreturn １；}int ＢinSearｃh（BinTable s ，KeyTｙpe k）｛ﻩint lｏw,mid , ｈiｇｈ；ﻩloｗ = 0 ；high = s、lｅngth-1 ;ｗｈile（low ＜= hiｇh）{ﻩﻩmid＝(ｌow+higｈ）／2 ；ﻩif(s、ｅlｅm［mｉd]、kｅy== k)ﻩﻩﻩretｕrｎｍiｄ;ﻩｅlse ｉｆ（s、elem[mｉd］、ｋｅy ＞ｋ）ﻩﻩhiｇh＝ mｉｄ－ 1 ;ﻩﻩｅlｓeﻩlow = mid +1 ；ﻩ｝ﻩrｅturn —1；}ｖoiｄ main（)｛PBinTablｅ p ；ﻩintｉ ,n ；ﻩKeyType ａ;p ＝Iｎit＿BinＴable（）;ｃｏuｔ<<”请输入数据个数：”;ｃｉn〉＞n；ﻩｃout<〈"请按从小到大得顺序输入数据：”〈<ｅndｌ；fｏr(i = 0 ；ｉ〈 n; i ++）ﻩ｛ｃin>〉a;ﻩinsert_BinTable（ｐ，a）;｝ﻩcout＜<＂请输入要查找得数据,输入32767结束：” ;ﻩcin〉＞ａ ;whilｅ（a！= 3２767){ﻩi =BｉｎSeaｒｃh（*p , ａ）；iｆ（ｉ =＝-1）ﻩ{ﻩﻩcｏut〈〈＂无此数据！请重新输入:＂〈〈ｅndl ;ｃiｎ>>a;ﻩ}ﻩelｓe{ﻩcout＜<"该数据得位置就是：”〈<i+1〈＜ｅndl ；ﻩﻩﻩｃｏut＜〈”请输入要查找得数据:" ；cin＞〉a ;}ﻩ}｝。

折半查找所描述的算法折半查找，也称为二分查找，是一种在有序数组中查找目标元素的算法。

它的基本思想是在每一步中将目标值与数组中间元素进行比较，从而缩小待查找范围，直到找到目标值或者确定目标值不存在。

具体的折半查找算法可以描述为以下几个步骤：1.确定查找范围：首先确定待查找元素所在的起始和结束位置。

一般情况下，初始条件下起始位置为0，结束位置为数组的长度减12. 计算中间位置：通过计算起始位置和结束位置的中间索引，可以得到中间位置mid。

中间位置可以通过如下公式获得：mid = (start + end) / 23. 检查中间元素：将目标元素与中间元素进行比较。

如果目标元素等于中间元素，则查找成功并返回中间位置。

如果目标元素小于中间元素，则新的结束位置为mid-1、如果目标元素大于中间元素，则新的起始位置为mid+14.更新查找范围：根据目标元素与中间元素的比较结果，更新起始位置和结束位置，然后重复步骤2和步骤3，直到查找成功或者待查找范围为空。

5.查找失败：如果查找范围为空，即起始位置大于结束位置，则表示查找失败。

折半查找算法的时间复杂度是O(logn)，其中n是数组的长度。

这是由于每一次迭代都将查询范围缩小一半，所以最多需要进行logn次迭代。

下面是一个使用折半查找算法查找目标元素在有序数组中的位置的示例代码：```pythondef binary_search(arr, target):start = 0end = len(arr) - 1while start <= end:mid = (start + end) // 2if arr[mid] == target:return midelif arr[mid] < target:start = mid + 1else:end = mid - 1return -1#测试arr = [1, 3, 5, 7, 9, 11]target = 7result = binary_search(arr, target)if result != -1:print("目标元素在数组中的位置为", result)else:print("数组中不存在目标元素")```在上面的示例代码中，我们首先定义了一个binary_search函数。

折半查找的实验报告折半查找的实验报告引言：在计算机科学领域，查找是一项基本操作。

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

本实验旨在通过实际操作和数据分析，探究折半查找算法的原理和性能。

实验设计：本次实验使用C++语言来实现折半查找算法，并通过编写测试程序来验证算法的正确性和性能。

我们使用了一个已排序的整数数组，其中包含了10000个元素。

实验过程中，我们将记录算法的查找次数和运行时间，并与线性查找算法进行对比。

实验步骤：1. 首先，我们定义一个包含10000个已排序整数的数组，并选择一个待查找的目标值。

2. 接下来，我们实现折半查找算法。

该算法的基本思想是将待查找的目标值与数组的中间元素进行比较，如果相等则返回找到的位置，如果目标值小于中间元素，则在左半部分继续查找，否则在右半部分继续查找。

重复这个过程，直到找到目标值或者确定目标值不存在。

3. 我们编写测试程序，分别使用折半查找算法和线性查找算法来查找目标值，并记录查找次数和运行时间。

4. 重复多次实验，以获得更准确的结果。

同时，我们还可以改变目标值的位置，观察算法的性能变化。

实验结果：经过多次实验，我们得到了如下结果：- 折半查找算法的平均查找次数为log2(10000)≈13次，而线性查找算法的平均查找次数为10000次。

- 折半查找算法的平均运行时间为0.0001秒，而线性查找算法的平均运行时间为0.01秒。

- 当目标值位于数组的中间位置时，折半查找算法的性能最佳；而当目标值位于数组的两端时，折半查找算法的性能最差。

讨论与分析：通过对实验结果的分析，我们可以得出以下结论：1. 折半查找算法的时间复杂度为O(log n)，而线性查找算法的时间复杂度为O(n)。

因此，折半查找算法在大规模数据中的查找效率远高于线性查找算法。

2. 折半查找算法适用于已排序的数据集，而线性查找算法对数据集的有序性没有要求。

因此，在已排序的数据集中使用折半查找算法可以提高查找效率。

折半查询一、实验目的1，掌握排序算法及基本思想及实现的技术；能够根据实际问题特点的要求选择合理的排序方法，理解排序在数据处理中的重要性；2.学会比较各种排序方法的稳定性分析以及在最好、最坏和平均情况的时间性能分析。

3.掌握顺序查找和折半查找两种查找的算法及实现技术；了解它们各自的优缺点。

4.熟悉各种查找方法的适用范围和条件；掌握顺序查找、折半查找的基本思想及效率分析。

二、实验环境1.硬件：每个学生需配备计算机一台。

操作系统：DOS或Windows2.软件：DOS或Windows操作系统+Turbo C;三、实验要求1.本次实验较为简单，每个同学独立按时完成，通过实验掌握记录的概念，为以后数据库技术打好基础。

2.如果输入数据较为繁琐，可减低每个班的人数。

3.输入输出数据要有提示，方便用户操作。

四、实验内容1.现在某个学院有20名同学分属于2个班级（Class1和Class2，每个班有10名同学，每个同学记录包括：班级、学号、姓名、性别、电话号码等信息）。

2.以学号为主关键字，以班级为次关键字，建立一个顺序表，表中的每个数据元素是一个记录，其中的某个域用来存储关键字的值，按关键字的值进行顺序查找。

为分析排序方法的稳定性，关键字可用次关键字。

#include"stdio.h"#include"malloc.h"#include"string.h"typedef struct{int cla;int num;char name[7];char sex;long phnum;}stu_hc;typedef struct{stu_hc *elem;int length;int sum;}sqlist_hc;sqlist_hc *initlist_hc(){sqlist_hc *l;int n;l=(sqlist_hc*)malloc(sizeof(sqlist_hc));if(!l)printf("出错!\n");printf("输入学生人数:");scanf("%d",&n);l->length=0;l->sum=n;l->elem=(stu_hc*)malloc(n*sizeof(stu_hc));if(!l->elem)printf("出错!\n");return(l);}int place_hc(sqlist_hc *l,int c,int num){int low,high,mid,j=-1,i;low=0;high=l->length-1;while(low<=high){mid=(low+high)/2;if(l->elem[mid].num>num)high=mid-1;else{j=mid;low=mid+1;}}i=j;for(j=mid;j>=i;j--){if(j==-1||num>l->elem[j].num)break;else if(num==l->elem[j].num&&c>l->elem[j].cla)break;} return(++j);}void move_hc(sqlist_hc *l,int j){int i;for(i=l->length-1;i>=j;i--){l->elem[i+1].cla=l->elem[i].cla;strcpy(l->elem[i+1].name,l->elem[i].name);l->elem[i+1].num=l->elem[i].num;l->elem[i+1].sex=l->elem[i].sex;l->elem[i+1].phnum=l->elem[i].phnum;}}void createlist_hc(sqlist_hc *l){int i,j,c,num;char nam[7],s;long p;printf("输入学生信息(class name num sex phonenum):\n"); for(i=0;i<l->sum;i++){flushall();scanf("%d %s %d %c %ld",&c,nam,&num,&s,&p);j=!(l->length)?0:place_hc(l,c,num);move_hc(l,j);l->elem[j].cla=c;strcpy(l->elem[j].name,nam);l->elem[j].num=num;l->elem[j].sex=s;l->elem[j].phnum=p;l->length++;}}void seekstu_hc(sqlist_hc *l){int low,high,mid,num,c;printf("输入查找人的学号和班级号:");scanf("%d %d",&num,&c);while(num!=-1||c!=-1){low=0;high=l->length-1;while(low<=high){mid=(low+high)/2;if(l->elem[mid].num<num)low=mid+1;else if(l->elem[mid].num>num)high=mid-1;else{if(l->elem[mid].cla<c)mid++;else if(l->elem[mid].cla>c)mid--;break;}}printf("%d,%s,%d,%c,%ld\n",l->elem[mid].cla,l->elem[mid].name,l->elem[mid].num,l->elem[mid].sex,l->elem[ mid].phnum);printf("输入查找人的学号和班级号:");scanf("%d %d",&num,&c);}}void printlist_hc(sqlist_hc*l){int i,j=0;printf("当前表中信息如下:class/name/num/sex/phonenum\n");for(i=0;i<l->sum;i++){printf("%d/%s/%d/%c/%ld",l->elem[i].cla,l->elem[i].name,l->elem[i].num,l->elem[i].sex,l->elem[i].phnum);if(++j==3){j=0;printf("\n");}}printf("\n");}main(){sqlist_hc *l;l=initlist_hc();createlist_hc(l);printlist_hc(l);seekstu_hc(l);printf("作者:黄晨");}。

折半查找法c语言【折半查找法（BinarySearch）是一种基于折半原理（分治思想）的搜索算法，它是用来定位一个给定值在已排序的数据结构中的位置。

折半查找法的步骤：（1）在有序表中取一个中间位置的记录（折半点）；（2）如果待查记录和折半点记录相等，则查找成功，否则；（3）如果待查记录小于折半点记录，则在折半点的左半区继续折半查找；（4）如果待查记录大于折半点记录，则在折半点的右半区继续折半查找；（5）重复上述过程，直到找到待查记录或查找范围为空；（6）若查找范围为空，则表示待查记录不在表中，查找失败。

折半查找的查找步骤比较简单，它的时间复杂度为O(log2n)，是相对于普通查找算法更有效率的一种搜索算法。

c语言中可以使用for循环、while循环或者recursive函数来实现折半查找法，以下是一个以循环方式实现的折半查找法代码：int Binary_Search(int arr[], int key, int left, int right) {int mid;while(left <= right){mid = (left + right) / 2;if (key == arr[mid]){return mid;}else if (key < arr[mid]){right = mid - 1;}else{left = mid + 1;}}return -1; //找失败}因为折半查找的最终查找范围只可能是一个记录，或是空，所以当right<left时，说明查找范围内没有元素，即查找失败。

折半查找法要求数据项必须处于排序状态，另外折半查找法只适用于静态查找表，对于需要频繁插入或删除的数据，折半查找法就不再适用了。

也就是说，若要使用折半查找法，就要求数据项必须处于排序状态，且数据表的大小不应该有太大变化，这样才能得到较好的查找效率。

折半查找法可用于多种数据结构中，如顺序表、单链表、二叉树等，这些数据结构中必须满足两个条件：（1）必须可以随机访问，即可以根据索引或下标随机访问某个元素；（2）数据结构必须已排序。

顺序查找与折半查找实验报告姓名：许严班级：计122 学号：12130230501.问题描述实现顺序查找与折半查找的程序设计，并比较两种查找方法的性能。

2.基本要求（1）设计查找表的存储结构。

（2）设计查找算法，对同一组实验数据实现查找。

（3）输入：查找表的数据个数和数据由键盘输入，数据元素类型为整型，以菜单方式选择顺序查找或折半查找中的一种，并由键盘输入想要查找的数据。

（4）输出：若查找成功输出其位置和查找次数，若查找失败输出信息和查找次数。

3.实现提示（1）存储设计由于要对一组实验数据实现顺序查找与折半查找，只能采用顺序表存放查找表数据，存储结构定义与教材一致。

设关键字类型为整型，利用前面实验建立的线性表类，生成一个线性表对象，线性表中的数据个数、数据以及待查找的数据由键盘输入。

（2）算法设计由于折半查找法要求数据是有序的，可设立一个创建有序顺序表的函数Sort(int*fp,int length)；设立一个顺序查找函数SequenSearch(int*fp,int length)实现顺序查找；设立一个折半查找函数实现折半查找；编写一个主函数main(),在主函数中设计一个简单的菜单，根据用户的选择分别调用顺序查找和折半查找算法。

4.程序设计(1) using namespace std;struct Node{int key;};class SSearch{private:Node *ST;int len;public:SSearch();~SSearch();void Create(int n);void Display();void Sort();void Sort_n(int arr[]);void SequenceSearch(int key);void Search(int key);};SSearch::SSearch(){ST=0;len=0;}SSearch::~SSearch(){if(ST) delete[]ST;len=0;}void SSearch::Create(int n){len=n;ST=new Node[len];cout<<"请输入"<<n<<"个数据元素：\n";int i=0;while(i<len){cin>>ST[i].key;i++;}cout<<"静态表创建成功！：）\n";}void SSearch::Display(){cout<<"表中数据元素依次为：\n";for(int i=0;i<len;i++)cout<<ST[i].key<<'\t';cout<<endl;}voidSSearch::Sort() //冒泡排序{int t;for(int i=1;i<len;i++){bool y=1;for(int j=0;j<len-i;j++){if(ST[j].key>ST[j+1].key){t=ST[j].key;ST[j].key=ST[j+1].key;ST[j+1].key=t;y=0;}}if(y) return;}}void SSearch::Sort_n(int arr[]){int t;for(int i=1;i<len;i++){bool y=1;for(int j=0;j<len-i;j++){if(arr[j]>arr[j+1]){t=arr[j];arr[j]=arr[j+1];arr[j+1]=t;y=0;}}if(y) return;}}void SSearch::SequenceSearch(int key){ST[0].key=key;int count=1,i=len-1; //计数边梁count为1的原因是下面的for语句先判定在count++ for(;ST[i].key!=key;i--,count++);if(i){cout<<"查找成功！\n在顺序表的第"<<i<<"个位置（从0开始），一共比较了"<<count<<"次。

实验报告课程名称：数据结构与算法课程类型：必修实验项目：树型查找结构与排序方法实验题目：BST存储结构与折半查找一、实验目的1. 理解二叉查找树的存储结构。

2. 掌握BST的插入、删除、查找、排序等多种算法。

3. 掌握折半查找算法。

4. 学会计算BST的查找成功及失败的平均查找长度。

5. 学会计算折半查找的查找成功及失败的平均查找长度。

二、实验要求及实验环境实验要求：1. 设计BST 的左右链存储结构，并实现BST插入（建立）、删除、查找和排序算法。

2. 实现折半查找算法。

3. 实验比较：设计并产生实验测试数据，考察比较两种查找方法的时间性能，并与理论结果进行比较。

以下具体做法可作为参考：4. 第1组测试数据： n=1024个已排序的整数序列（如0至2048之间的奇数）；第2组测试数据：第1组测试数据的随机序列。

5. 按上述两组序列的顺序作为输入顺序，分别建立BST。

6. 编写程序计算所建的两棵BST的查找成功和查找失败的平均查找长度（主要是改造Search算法，对“比较”进行计数），并与理论结果比较。

7. 以上述BST的中序遍历序列作为折半查找的输入，编写程序分别计算折半查找的查找成功和查找失败的平均查找长度，并与理论结果比较。

8. 以上实验能否说明：就平均性能而言，BST的查找与折半查找差不多，为什么？实验环境：codeblocks/Dev-C++三、设计思想（本程序中的用到的所有数据抽象数据性ADT的定义，主程序的流程图及各程序模块之间的调用关系）1. 所用的抽象数据性ADT的定义1）逻辑结构：BST树：二叉查找树是一个满足以下条件的树：任意一个结点的关键字，都大于(小于)其左(右)子树中任意结点的关键字，因此各结点的关键字互不相同按中序遍历二叉查找树所得的中序序列是一个递增的有序序列，因此，二叉查找树可以把无序序列变为有序序列。

同一个数据集合，可按关键字表示成不同的二叉查找树，即同一数据集合的二叉查找树不唯一；但中序序列相同。

折半查找的实验报告
《折半查找的实验报告》
在计算机科学领域中，折半查找是一种常用的搜索算法，也被称为二分查找。

它的原理是在有序数组中查找特定元素的位置，通过将数组分成两部分并逐步
缩小搜索范围来实现。

本实验旨在验证折半查找算法的效率和准确性，以及探
讨其在实际应用中的优势和局限性。

实验过程分为以下几个步骤：
1. 数据准备：首先，我们准备了多组有序数组作为输入数据，每组数组包含不
同数量的元素。

这些数组涵盖了各种规模的数据集，以便全面测试折半查找算
法的性能。

2. 算法实现：我们编写了折半查找算法的实现代码，并在不同规模的数据集上
进行了测试。

算法的实现包括了边界条件的处理、搜索范围的缩小和结果的返
回等关键步骤。

3. 实验设计：为了验证折半查找算法的准确性和效率，我们设计了一系列实验，包括查找存在的元素、查找不存在的元素以及对比折半查找和线性查找算法的
性能。

4. 实验结果：通过对实验数据的分析和对比，我们得出了折半查找算法在不同
规模数据集上的搜索耗时和准确率。

同时，我们也探讨了折半查找算法相对于
线性查找算法的优势和局限性。

5. 结论与展望：最后，我们总结了实验结果，并对折半查找算法在实际应用中
的潜在价值和改进方向进行了展望。

通过本次实验，我们对折半查找算法有了更深入的理解，同时也为其在实际应
用中的优化和推广提供了一些思路。

希望本实验报告能够对相关领域的研究和应用有所启发，为进一步探索折半查找算法的性能和潜力提供参考。

数据结构50：⼆分查找法（折半查找法）折半查找，也称⼆分查找，在某些情况下相⽐于顺序查找，使⽤折半查找算法的效率更⾼。

但是该算法的使⽤的前提是静态查找表中的数据必须是有序的。

例如，在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使⽤折半查找算法查找数据之前，需要⾸先对该表中的数据按照所查的关键字进⾏排序：{5,13,19,21,37,56,64,75,80,88,92}。

在折半查找之前对查找表按照所查的关键字进⾏排序的意思是：若查找表中存储的数据元素含有多个关键字时，使⽤哪种关键字做折半查找，就需要提前以该关键字对所有数据进⾏排序。

折半查找算法对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采⽤折半查找算法查找关键字为 21 的过程为：图 1 折半查找的过程（a）如上图 1 所⽰，指针 low 和 high 分别指向查找表的第⼀个关键字和最后⼀个关键字，指针 mid 指向处于 low 和 high 指针中间位置的关键字。

在查找的过程中每次都同 mid 指向的关键字进⾏⽐较，由于整个表中的数据是有序的，因此在⽐较之后就可以知道要查找的关键字的⼤致位置。

例如在查找关键字 21 时，⾸先同 56 作⽐较，由于21 < 56，⽽且这个查找表是按照升序进⾏排序的，所以可以判定如果静态查找表中有 21这个关键字，就⼀定存在于 low 和 mid 指向的区域中间。

因此，再次遍历时需要更新 high 指针和 mid 指针的位置，令 high 指针移动到 mid 指针的左侧⼀个位置上，同时令 mid 重新指向 low 指针和 high 指针的中间位置。

如图 2 所⽰：图 2 折半查找的过程（b）同样，⽤ 21 同 mid 指针指向的 19 作⽐较，19 < 21，所以可以判定 21 如果存在，肯定处于 mid 和 high 指向的区域中。

所以令 low 指向 mid 右侧⼀个位置上，同时更新 mid 的位置。

深圳大学实验报告课程名称：数据结构实验项目名称：查找排序之折半查找学院：信息工程学院专业：电子信息工程指导教师：报告人：学号：2009100000 班级：电子1班实验时间：2011年12月2日实验报告提交时间：2011年12月13日教务处制//调用函数Search_Bin，并将函数返回结果放在i中i = Search_Bin(Data, Dnum, skey);printf("----------------------------------------\n");if(i==-1) //若Search_Bin返回值为-1则显示查找失败printf("查找失败!\n");else //不然则执行下面语句{printf("查找成功!\n");printf("查找的数据位置在(%d)\n",i);}printf("查找次数(%d)",icount);printf("\n");return 0;}四、实验结论：实结果图：情况一、能够在待查数组中查找到待查元素情况二、不能够在待查数组中查找到待查元素数据分析基于上面程序运行图可以很明显得知整个算法的实现过程，针对第一个图：1、首先建立一个数组存放待查元素2、针对定值key进行折半查找，第一个图可以得到key=113、mid=（low+high）/2 =（0+5）/2 =2.得到的是ST[2]=33,查找了一次4、判断ST[2]=33大于key=11，即执行high=mid-1=15、mid=（low+high）/2 =（0+1）/2 =0.得到的是ST[0]=11=key，查找成功，查找了两次6、返回待查元素所在位置7、同理。

若查找不成功则返回查找失败五、实验体会：本次实验很简单，只要掌握折半查找算法的原理，那么剩下的就是花时间编写代码和调试程序。