下载文档原格式
先看看这个，下面有例子折半查找：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
算法要求算法复杂度下面提供一段二分查找实现的伪代码:BinarySearch(max,min,des)mid-<(max+min)/2while(min<=max)mid=(min+max)/2if mid=des thenreturn midelseif mid >des thenmax=mid-1elsemin=mid+1return max折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。
它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。
如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。
如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。
二分查找法一般都存在一个临界值的BUG，即查找不到最后一个或第一个值。
可以在比较到最后两个数时，再次判断到底是哪个值和查找的值相等。
C语言代码int BinSearch(SeqList * R，int n , KeyType K ){ //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1int low=0，high=n-1，mid；//置当前查找区间上、下界的初值if(R[low].key==K){return low ;}if(R[high].key==k)return high;while(low<=high){ //当前查找区间R[low..high]非空mid=low+((high-low)/2)；//使用(low + high) / 2 会有整数溢出的问题（问题会出现在当low + high的结果大于表达式结果类型所能表示的最大值时，这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)不存在这个问题if(R[mid].key==K){return mid；//查找成功返回}if(R[mid].key>K)high=mid-1; //继续在R[low..mid-1]中查找elselow=mid+1；//继续在R[mid+1..high]中查找}if(low>high)return -1；//当low>high时表示查找区间为空，查找失败} //BinSeareh折半查找程序举例程序要求：1.在main函数中定义一个20个元素的int数组，完成初始化和显示操作。
二分查找是在我们整个数据结构当中一个比较重要的算法，它的思想在我们的实际开发过程当中应用得非常广泛。
在实际应用中，有些数据序列是已经经过排序的，或者可以将数据进行排序，排序后的数据我们可以通过某种高效的查找方式来进行查找，今天要讲的就是折半查找法(二分查找)，它的时间复杂度为O(logn)，将以下几个方面进行概述了解二分查找的原理与思想分析二分查找的时间复杂度掌握二分查找的实现方法了解二分查找的使用条件和场景1 二分查找的原理与思想在上一个章节当中，我们学习了各种各样的排序的算法，接下来我们就讲解一下针对有序集合的查找的算法—二分查找（Binary Search、折半查找）算法，二分查找呢，是一种非常容易懂的查找算法，它的思想在我们的生活中随处可见，比如说：同学聚会的时候喜欢玩一个游戏——猜数字游戏，比如在1-100以内的数字，让别人来猜从，猜的过程当中会被提示是猜大了还是猜小了，直到猜中为止。
这个过程其实就是二分查找的思想的体现，这是个生活中的例子，在我们现实开发过程当中也有很多应用到二分查找思想的场景。
比如说仙现在有10个订单，它的金额分别是6、12 、15、19、24、26、29、35、46、67 请从中找出订单金额为15的订单，利用二分查找的思想，那我们每一次都会与中间的数据进行比较来缩小我们查找的范围，下面这幅图代表了查找的过程，其中low，high代表了待查找的区间的下标范围，mid表示待查找区间中间元素的下标（如果范围区间是偶数个导致中间的数有两个就选择较小的那个）第一次二分查找第二次二分查找第三次二分查找通过这个查找过程我们可以对二分查找的思想做一个汇总：二分查找针对的是一个有序的数据集合，查找思想有点类似于分治思想。
每次都通过跟区间的中间元素对比，将待查找的区间范围缩小为原来的一半，直到找到要查找的元素，或者区间被缩小为0。
一：查找的数据有序二：每次查找，数据的范围都在缩小，直到找到或找不到为止。
实验五查找的应用一、实验目的：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. Fibonacci4. 分块查找静态查找可以⽤线性表结构组织数据，这样可以使⽤顺序查找算法，再对关键字进⾏排序就可以使⽤折半查找或斐波那契查找等算法提⾼查找效率，平均查找长度：折半查找最⼩，分块次之，顺序查找最⼤。
顺序查找对有序⽆序表均适⽤，折半查找适⽤于有序表，分块查找要求表中元素是块与块之间的记录按关键字有序动态查找是数据集合需要添加删除元素的查找包括： 1. ⼆叉排序树 2. 平衡⼆叉树 3. 散列表 顺序查找适合于存储结构为顺序存储或链接存储的线性表。
顺序查找属于⽆序查找算法。
从数据结构线形表的⼀端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相⽐较，若相等则表⽰查找成功 查找成功时的平均查找长度为： ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 顺序查找的时间复杂度为O(n)。
元素必须是有序的，如果是⽆序的则要先进⾏排序操作。
⼆分查找即折半查找，属于有序查找算法。
⽤给定值value与中间结点mid的关键字⽐较，若相等则查找成功；若不相等，再根据value 与该中间结点关键字的⽐较结果确定下⼀步查找的⼦表 将数组的查找过程绘制成⼀棵⼆叉树排序树，如果查找的关键字不是中间记录的话，折半查找等于是把静态有序查找表分成了两棵⼦树，即查找结果只需要找其中的⼀半数据记录即可，等于⼯作量少了⼀半，然后继续折半查找，效率⾼。
根据⼆叉树的性质，具有n个结点的完全⼆叉树的深度为[log2n]+1。
尽管折半查找判定⼆叉树并不是完全⼆叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为[log2n]+1，最好的情况是1次。
时间复杂度为O(log2n)； 折半计算mid的公式 mid = (low+high)/2;if(a[mid]==value)return mid;if(a[mid]>value)high = mid-1;if(a[mid]<value)low = mid+1; 折半查找判定数中的结点都是查找成功的情况，将每个结点的空指针指向⼀个实际上不存在的结点——外结点，所有外界点都是查找不成功的情况，如图所⽰。
折半查找法的查找速度一定比顺序查找法快。
不能笼统的说那个算法一定就好，算法分析要看条件和模型。
折半算法要求待查区域数据是已经排好序的，但是顺序查找没这个要求。
算法时间分析要看平均情况、最坏情况、最好情况的。
最好情况两者
时间一样，因为都是比较方法查找，都假定第一次比较就找到。
最坏情况，折半查找更优为log n次比较，而顺序查找为n次比较。
平均情况下（所
有待查元素查找概率相当），一般是折半查找由于顺序查找（O(log n) < O(n)）。
一般数据规模稍大的测试、算法练习题，折半查找表现都很好，常常
优于顺序查找，毕竟顺序查找算不上什么高等算法，优化空间很小。
但是，实际的查找操作很复杂，并不是查找数量多了就会趋近于平均
情况，而且折半查找又要求有排序，所以仍然需要按照系统需求进行相应
的数学分析和实际检测。
排序算法：折半插⼊排序算法分析：（1）时间复杂度 从时间上⽐较，折半查找⽐顺序查找快，所以就平均性能来说，折半插⼊排序优于直接插⼊排序。
折半插⼊排序所需要的关键字⽐较次数与待排序序列的初始排列⽆关，仅依赖于记录的个数。
不论初始序列情况如何，在插⼊第i个记录时，需要经过logi+1(向下取整+1)次⽐较，才能确定它插⼊的位置。
所以当记录的初始排列为正序或接近正序时，直接插⼊排序⽐折半插⼊排序执⾏的关键字⽐较次数要少。
折半插⼊排序的对象移动次数与直接插⼊排序相同，依赖于对象的初始排列。
在平均情况下，折半插⼊排序仅减少了关键字的⽐较次数，⽽记录的移动次数不变。
因此，折半插⼊排序的时间复杂度仍然为O（n^2）。
（2）空间复杂度 折半插⼊排序所需附加存储空间和直接插⼊排序相同，只需要⼀个记录的辅助空间r[0]，所以空间复杂度为O（1）算法特点：（1）是稳定排序。
（2）因为要进⾏折半插⼊查找，所以只能⽤于顺序结构，不能⽤于链式结构。
（3）适合初始记录⽆序、n较⼤的情况。
#include<iostream>#include<vector>using namespace std;void BSort(int a[],int n){for (int i = 1; i < n; i++)//数组中的第⼀个元素最为已经排好的序列，所以从数组的第⼆个元素开始排{int key = a[i];//带插⼊元素int low = 0, high = i - 1;while (low <= high){int mid = (low + high) / 2;if (key < a[mid]){high = mid - 1;}else{low = mid + 1;}}for (int j = i - 1; j >= high + 1; j--){//i-1是已经排好序的序列的数量，high+1是待插⼊的的位置，元素后移腾出high+1这个位置a[j + 1] = a[j];}a[high + 1] = key;}}int main(){int a [11] = { 2,6,4,5,54,53,53,5,34,34,32};BSort(a, 11);for (int i = 0; i < 11; i++){cout << a[i] << " ";}return 0;}。
数据结构复习--排序和查找现在正在学习查找和排序，为了节省时间提⾼效率，就正好边学习边整理知识点吧！知识点⼀：⼆分查找/折半查找1.⼆分查找的判定树（选择题）下列⼆叉树中，可能成为折半查找判定树（不含外部结点）的是： (4分)1.2.3.4.注：折半查找判定树是⼀棵⼆叉排序树，它的中序遍历结果是⼀个升序序列，可以在选项中的树上依次填上相应的元素。
虽然折半查找可以上取整也可以下取整但是⼀个查找判定树只能有⼀种取整⽅式。
如果升序序列是偶数个，那么终点应该偏左多右少。
在2选项中，由根节点左⼦树4个节点⽽右⼦树5个节点可以确定⽤的是向下取整策略，但是它的左⼦节点在左⼦树种对应的终点左边2个，右边个，明显是上取整策略，策略没有统⼀，所以是错的。
其他的选项类似分析。
2.⼆分查找法/折半查找法已知⼀个长度为16的顺序表L，其元素按关键字有序排列。
若采⽤⼆分查找法查找⼀个L中不存在的元素，则关键字的⽐较次数最多是： (2分)1. 72. 63. 54. 4 注：⼀次找到最边界的那⼀个树的情况下有最多次数 这个题中结点数16是个偶数：第⼀次（0+15）/2 7 第⼆次（8+15）/2 11第三次（12+15）/2 14 第四次（14+15）/2 14 第五次（15+15）/2 15（下取整的就向右计算求最多次数）第⼀次（0+15）/2 8 第⼆次（0+7）/2 4 第三次（0+3）/2 2 第四次（0+1)/2 0第五次（0+0）/2 0（下取整的话就向左求最多次数）若结点数是奇数15：第⼀次（0+14）/2 7 第⼆次（ 0+6）/2 3 第三次（0+2）/2 1第四次（0+0）/2 0第⼀次（0+14）/2 7 第⼆次（8+14）/2 11 第三次（12+14）/2 13第四次（14+14）/2 0这时候向左或者向右都是OK的（因为得到的数都是能够被2整除的）但是划重点了折半查找⼀个有序表中不存在的元素，若向下取整，则要最多⽐较[log2n]+1次，若向上取整，则要最多⽐较[log2(n+1)],其实就是求树的深度.（这⼀块⾃⼰的说法可能不够准确，希望⼤家看到有问题的可以指出来）结合实际，我们⽤[log2n]+1来算更简单并且计算[log2n]要取整数，因为可能会存在不是满⼆叉树的情况。
顺序查找与二分查找对比近年来，随着信息技术的迅猛发展，各行各业对于数据的处理和检索需求越来越大。
其中，查找是一种常见并且重要的操作。
在众多查找算法中，顺序查找和二分查找是两种常见的方法。
本文将对这两种查找算法进行对比，并探讨它们在实际应用中的优劣势。
一、顺序查找顺序查找，又称线性查找，是一种简单直观的查找方式。
它的基本思想是逐个比对待查找元素和列表中的元素，直到找到匹配的元素或遍历完整个列表。
顺序查找的实现相对简单，只需要从列表的第一个元素开始逐个比对即可。
然而，顺序查找的缺点也是很明显的。
随着待查找元素数量的增加，顺序查找的时间复杂度由O(1)线性增长至O(n)，其中n为待查找元素的个数。
这意味着当数据量较大时，顺序查找的效率将大幅下降。
尤其是对于有序列表，顺序查找无法充分利用列表的有序性，在查找效率上存在明显的不足。
二、二分查找二分查找，又称折半查找，是一种高效的有序查找算法。
它利用了有序列表的特性，通过比较待查找元素与有序列表中间位置元素的大小关系，来确定待查找元素可能存在的区间，从而迅速缩小查找范围。
基于这个思想，二分查找可以将查找的时间复杂度从O(n)降低到O(log₂(n))，其中n为列表中元素的个数。
相比于顺序查找，二分查找的优势主要体现在高效性和适用范围上。
对于大规模有序列表，二分查找能够迅速定位目标元素，大大减少了查找的时间成本。
此外，在对近乎有序或近似有序列表进行查找时，二分查找仍能有较好的表现。
然而，二分查找也有其限制之处，它要求列表必须是有序的，这就增加了排序的前置操作，并且仅适用于静态列表，即在查找过程中列表不发生变化。
三、实际应用中的对比在实际应用中，选择合适的查找算法需要考虑到数据规模、数据的有序性以及查找的频率等因素。
下面针对不同场景进行对比：1. 对于小规模或基本有序的数据集合，顺序查找往往是一个简单而直接的选择。
顺序查找代码简单，易于实现，并且不要求待查找元素有序，适用于轻量级的查找操作。
二分查找排序算法二分查找排序算法介绍二分查找也叫折半查找，是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，并重复该过程，直到找到该特定元素为止。
应用场景二分查找算法主要应用于有序数据集合，比如数字、字母等有序排列的数据。
时间复杂度由于每次查找都会将数据集合缩小一半，因此时间复杂度为O(log n)。
代码实现以下是Python实现的二分查找算法：```def binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1```其中`arr`为有序数组，`target`为要查找的目标值。
函数返回目标值在数组中的下标，若不存在则返回-1。
优化思路在实际应用中，我们可以对二分查找进行优化。
以下是一些优化思路：1. 查找区间的左右边界在每次查找时，我们可以记录当前查找区间的左右边界，这样可以减少不必要的比较操作。
2. 二分查找变形有时候我们需要查找第一个等于目标值的元素或者最后一个等于目标值的元素，这时候我们可以对二分查找进行一些变形。
例如，如果要查找第一个等于目标值的元素，在每次二分查找时，如果中间元素等于目标值，则更新右边界为中间元素下标；否则更新左边界为中间元素下标加1。
最终返回左边界即可。
3. 采用插值查找插值查找是对二分查找的一种优化。
它与二分查找类似，只是在每次查找时，将mid计算方式改为如下：```mid = low + (high - low) * (target - arr[low]) // (arr[high] -arr[low])这个公式就相当于将mid按照比例划分到low和high之间。
数据结构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 的位置。
详解排序算法（⼀）之3种插⼊排序（直接插⼊、折半插⼊、希尔）直接插⼊排序打过牌的⼈都知道，当我们拿到⼀张新牌时，因为之前的牌已经经过排序，因此，我们只需将当前这张牌插⼊到合适的位置即可。
⽽直接插⼊排序，正是秉承这⼀思想，将待插⼊元素与之前元素⼀⼀⽐较，从⽽找到合适的插⼊位置。
那么使⽤直接插⼊排序，具体是怎样操作的呢？我们取 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 来进⾏⽰范。
（1）第1轮排序，3之前⽆可⽐较值，因此我们从44开始操作，取44和3⽐较，⼤于3，顺序保持不变。
得数据3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（2）第2轮排序，取38和44⽐较，38 < 44，再将38与3⽐较，38 > 3，故将38放于第2位，得数据3, 38, 44, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（3）第3轮排序，取5与44⽐较，5 < 44，再将5与38⽐较，5 < 38，再将5与3⽐较，5 > 3, 置于第2位，得数据3, 5, 38, 44, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（4）如此经过14轮排序后，得到最终结果2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50动态图javascript实现function directInsertSort (arr) {let compare, // 对⽐元素下标current // 待插⼊元素值for (let i = 1; i < arr.length; i++) {current = arr[i]compare = i - 1while (current < arr[compare] && compare >= 0) {arr[compare + 1] = arr[compare]compare--}arr[compare + 1] = current}return arr}折半插⼊排序细⼼的同学可能已经注意到，当我们要将⼀个元素插⼊合适的位置时，其之前的元素是有序的，因此，我们可以⽤折半查找的⽅式来⽐对并插⼊元素，也就是所谓的折半插⼊排序。
C语言程序设计100例之（21）：折半查找例21 折半查找问题描述顺序查找是一种最简单和最基本的检索方法。
其基本思想是：从检索表的一端（如表中第一个记录或最后一个记录）开始，逐个进行记录的关键字和给定值的比较。
若某个记录的关键字和给定值比较相等，则查找成功；否则，若直至检索表的另一端（如最后一个记录或第一个记录），其关键字和给定值比较都不等，则表明表中没有待查记录，查找不成功。
顺序查找可以写成一个简单的一重循环，循环中依次将检索表（不妨设为数组a）中的元素与给定值比较，若相等，用break退出循环。
算法描述为：for (i=0; i< n;i++)if (a[i]==x) break;这样，循环结束后，若循环控制变量i小于数组元素个数n，则查找成功；否则，查找失败。
顺序查找实现简单，但效率不高。
当待查找序列有序时，即各检索表中元素的次序是按其记录的关键字值的大小顺序存储的。
此时采用折半查找会大幅提高查找效率。
折半查找的基本思想是先确定待查数据的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
具体做法是：先取数组中间位置的数据元素与给定值比较。
若相等，则查找成功；否则，若给定值比该数据元素的值小（或大），则给定值必在数组的前半部分（或后半部分），然后在新的查找范围内进行同样的查找。
如此反复进行，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。
因此，折半查找每查找一次，或成功，或使查找数组中元素的个数减少一半，当查找数组中不再有数据元素时，查找失败。
输入一个整数，在给定的有序数组中查找该整数是否存在，若存在，给出其数组的下标；若不存在，输出查找不成功信息。
输入格式第一行是一个正整数N (1 ≤N ≤100000)，代表数组中元素的个数。
第二行有N个整数，这N个整数从小到大排列好了。
第三行是一个整数M，代表待查找元素的个数。
接下来的M行，每行有一个整数x，表示每个待查找的元素。
实验5 排序与折半查找
实验人：叶展望学号:Xb14680101 时间：12.21
一、实验目的：
1.掌握顺序查找、折半查找算法的思想及高级语言程序实现方法；
2.掌握插入类排序的思想及程序实现方法。
二、实验内容：
对已给出的关键字序列进行排序后，在折半查找某关键字值。
三、实验步骤：
从键盘输入若干关键字值（可以是整数），然后对它们采用一趟直接插入排序后，输入待查找的数，查找成功返回该数的位置、查找失败返回错误信息。
四、主程序代码
#include <stdio.h>
#define LENGTH 10
int source[LENGTH] = {10,12,28,37,54,65,69,86,90,98};
//二分查找，查找key在原始数据a中的位置
int BinarySearch(int a[],int n,int key){
int low,high,mid;
low = 0;
high = n-1;
while(low<=high){
mid = (low + high)/2; //每次让中间数取最小和最大的中间
if(a[mid] == key) //查找的元素正好等于中间值
return mid;
else if(key < a[mid]) //查找的元素小于中间值，在最小值和上次中间值范围内查找
high = mid - 1;
else
low = mid + 1; //查找的元素大于中间值，在中间值和最大值范围查找
}
return -1;
}
int main(){
int i,key,pos;
printf("原始数据：\n");
for(i = 0 ; i < LENGTH ; i++)
printf("%d ",source[i]);
printf("\n请输入要查找的数据：");
scanf("%d",&key);
pos = BinarySearch(source,LENGTH,key);
if(pos > -1)
printf("\n查找成功，查找元素位于第 %d 个",pos); else
printf("\n查找失败");
}。
