下载文档原格式
单片机常用算法设计详解一、排序算法排序是将一组数据按照特定的顺序进行排列的过程。
在单片机中，常见的排序算法有冒泡排序、插入排序和快速排序。
冒泡排序是一种简单直观的排序算法。
它通过反复比较相邻的两个元素，如果顺序不对则进行交换，直到整个数组有序。
这种算法的优点是实现简单，容易理解，但效率较低，对于大规模数据的排序不太适用。
插入排序的基本思想是将待排序的元素插入到已经有序的部分中。
它从第二个元素开始，将其与前面已排序的元素进行比较，并插入到合适的位置。
插入排序在小规模数据时表现较好，但其平均和最坏情况下的时间复杂度不如快速排序。
快速排序则是一种高效的排序算法。
它选择一个基准元素，将数组分为小于和大于基准元素的两部分，然后对这两部分分别进行快速排序。
快速排序在大多数情况下具有较好的性能，但在最坏情况下可能会退化为 O(n²)的时间复杂度。
在单片机中选择排序算法时，需要根据数据规模和对时间效率的要求进行权衡。
二、查找算法查找是在一组数据中寻找特定元素的过程。
常见的查找算法有顺序查找和二分查找。
顺序查找是从数组的开头依次比较每个元素，直到找到目标元素或遍历完整个数组。
它适用于数据无序的情况，但效率较低。
二分查找则要求数组必须是有序的。
通过不断将数组中间的元素与目标元素进行比较，缩小查找范围，直到找到目标元素。
二分查找的时间复杂度为 O(log n)，效率较高，但需要数据有序。
在单片机应用中，如果数据经常需要查找且能保持有序，应优先考虑二分查找。
三、数据压缩算法在单片机系统中，为了节省存储空间和传输带宽，常常需要使用数据压缩算法。
常见的数据压缩算法有哈夫曼编码和 LZW 编码。
哈夫曼编码是一种无损数据压缩算法。
它根据字符出现的频率构建一棵哈夫曼树，然后为每个字符生成唯一的编码。
频率高的字符编码较短，频率低的字符编码较长，从而实现数据压缩。
LZW 编码则是一种字典编码算法。
它通过建立一个字典，将重复出现的字符串用较短的编码表示，从而达到压缩的目的。
常用算法解析及其应用场景算法是计算机科学中最基础的概念之一。
在日常生活中，我们无时无刻不在接触着各种算法，从谷歌搜索到智能手机里各种APP的推荐算法，都离不开算法的支持和应用。
在这篇文章中，我将为大家介绍常用的算法和它们的应用场景。
一、排序算法排序算法是程序中最常用的一种算法，其目的是将数据按一定方式进行排列。
常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序和快速排序。
1、冒泡排序冒泡排序是一种简单的排序算法，它的思路是从头到尾扫描一遍需要排序的数据，每一次将相邻两个元素进行比较并交换位置。
这个过程类似于水泡在水中上浮，一遍扫描结束后，最大的元素就会像水泡一样浮到最上面。
冒泡排序的时间复杂度为O(n²)，如果需要排序的数据量很大，那么执行起来会比较慢。
不过它的优点在于代码简单易懂，并且实现起来很容易。
2、选择排序选择排序的思路是每次从数据中选择一个最小（或最大）的元素，并将其放置在序列的起始位置。
按照这样的方式，每次只需要找到一个元素，就可以将数据序列排列好。
选择排序的时间复杂度也为O(n²)，但它比冒泡排序要稍微快一点。
3、插入排序插入排序的思路是将数据分为已排序区间和未排序区间两部分。
不断地将未排序区间的元素逐一与已排序区间的元素相比较，找到合适的位置插入。
重复执行这个过程，最终就能将整个数据序列排列好。
插入排序的时间复杂度也为O(n²)，但它的执行速度相对于冒泡排序和选择排序要慢一些。
不过它的优点在于它在处理小数据量时非常高效，并且在排序过程中需要的额外内存很少。
4、归并排序归并排序的思路是将数据分成两个子序列，分别进行排序，最后将排序好的子序列进行合并。
在合并的过程中，需要使用到一个额外的数组来存储数据。
归并排序的时间复杂度为O(nlogn)，执行效率相对较高。
尤其是在处理大数据量时，它表现得十分出色。
5、快速排序快速排序的思路不同于以上几种排序算法，它是一种分治法的排序算法。
C语言常用算法程序汇总C语言是一门广泛应用于计算机编程的语言，具有较高的效率和灵活性。
在C语言中，常见的算法程序包括排序算法、查找算法、递归算法等等。
以下是一些常用的C语言算法程序的汇总：1.排序算法：-冒泡排序：通过多次迭代比较相邻元素并交换位置，将最大的元素逐渐移动到正确的位置。
-插入排序：将待排序的元素与已排序的部分依次比较并插入到正确的位置。
-选择排序：每次从待排序的元素中选择最小的元素并与已排序的部分交换位置。
-快速排序：通过选择一个基准元素，将数组划分为两个子数组进行递归排序。
2.查找算法：-顺序查找：逐个比较数组中的元素，直到找到目标元素或到数组末尾。
-二分查找：通过比较目标元素与数组中间元素的大小，逐步缩小范围，直到找到目标元素。
-哈希查找：通过散列函数将目标元素映射到哈希表的索引位置进行查找。
3.递归算法：-阶乘：通过递归调用自身计算一个正整数的阶乘。
-斐波那契数列：通过递归调用自身计算斐波那契数列的第n个数。
-二叉树遍历：通过递归调用自身遍历二叉树的各个节点。
4.图算法：- 最短路径算法：如Dijkstra算法和Floyd算法，用于计算图中两个节点之间的最短路径。
-拓扑排序：通过对有向无环图进行排序，使得所有的边从排在前面的节点指向排在后面的节点。
- 最小生成树：如Prim算法和Kruskal算法，用于找到图中连接所有节点的最小子树。
5.动态规划：-最长公共子序列：通过寻找两个字符串中的最长公共子序列，解决字符串匹配问题。
-背包问题：通过动态规划解决在给定容量下选取物品使得总价值最大的问题。
-最大子序列和：通过动态规划解决一个数组中选取连续子序列使得和最大的问题。
以上只是一些C语言中常用的算法程序的汇总，实际上，还有很多其他的算法，如逆波兰表达式、霍夫曼编码、最小割等等。
通过学习这些算法，可以更好地理解C语言的应用和开发。
⼆分查找与⼏种排序⽅法1. 递归⼆分查找2. 冒泡排序3. 选择排序4. 插⼊排序5. 归并排序6. 快速排序1、递归⼆分查找思想：使⽤⼆分查找的前提条件是数组元素必须已经排好序。
⼆分查找法⾸先将关键字与数组的中间元素进⾏⽐较，考虑下⾯三种情形：如果关键字⽐中间元素⼩，那么只需在前⼀半数组元素中进⾏递归查找；如果关键字与中间元素相等，则匹配成功，查找结束。
代码：public static int binarySearch(int[] list, int key){return binarySearch(list, key, 0, list.length - 1);}public static int binarySearch(int[] list, int key , int low, int high){//没有查找到if(low > high)return - low - 1;int mid = (low + high) / 2;if(key < list[mid]){return binarySearch(list, key, low, mid - 1);}else if(key == list[mid]){return mid;}else{return binarySearch(list, key, mid + 1, high);}}------------------------------------------------- 排序算法 ----------------------------------------------各排序算法的时间复杂度、空间复杂度、稳定性：（排序算法的稳定性：排序前后相等元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的）排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序 O(n^2) O(n^2) O(1)稳定选择排序 O(n^2) O(n^2) O(1)不稳定直接插⼊排序 O(n^2) O(n^2) O(1)稳定归并排序 O(nlogn) O(nlogn) O(n)稳定快速排序 O(nlogn) O(n^2) O(logn)不稳定堆排序 O(nlogn) O(nlogn) O(1)不稳定冒泡排序： 冒泡排序算法需要多次遍历数组（N-1次），在每次遍历中，⽐较连续相邻的元素。
查找算法在实际应用中的选择与优化在当今数字化的时代，数据的处理和检索变得日益重要。
无论是在庞大的数据库中寻找特定的信息，还是在程序中快速定位所需的元素，查找算法都扮演着关键的角色。
正确选择和优化查找算法，可以显著提高系统的性能和效率，为用户带来更好的体验。
查找算法的种类繁多，常见的有顺序查找、二分查找、哈希查找等。
每种算法都有其特点和适用场景。
顺序查找是最为简单直观的一种查找算法。
它依次遍历数据集合中的每个元素，直到找到目标元素或者遍历完整个集合。
这种算法的优点是实现简单，对于小型、无序的数据集合或者数据集合的元素分布没有明显规律的情况，是一种可行的选择。
然而，其缺点也很明显，当数据量较大时，查找效率会非常低。
二分查找则是一种在有序数据集合中进行高效查找的算法。
它通过不断将数据集合对半分割，逐步缩小查找范围，从而快速定位目标元素。
二分查找的效率很高，时间复杂度为 O(log n)。
但它的前提是数据集合必须是有序的，如果数据集合经常动态变化，维护其有序性可能会带来较大的开销。
哈希查找则是通过将关键码映射到一个固定的哈希表中，从而实现快速查找。
哈希查找的平均时间复杂度可以达到 O(1)，效率极高。
但哈希函数的设计至关重要，如果哈希函数设计不好，可能会导致大量的哈希冲突，从而影响查找效率。
在实际应用中，选择合适的查找算法需要综合考虑多个因素。
首先是数据量的大小。
如果数据量较小，顺序查找可能就足够了；而对于大规模的数据，二分查找或哈希查找可能更合适。
其次是数据的分布和有序性。
如果数据本身有序，二分查找会是很好的选择；如果数据无序且分布较为随机，哈希查找可能更能发挥优势。
此外，数据的动态变化情况也需要考虑。
如果数据经常插入、删除和修改，那么维护有序性可能会比较困难，此时哈希查找可能更适合。
而如果数据的更新操作相对较少，而查找操作频繁，那么可以在数据初始化时将其排序，然后使用二分查找。
除了选择合适的查找算法，对算法进行优化也是提高查找效率的重要手段。
数据结构中的查找算法总结静态查找是数据集合稳定不需要添加删除元素的查找包括：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; 折半查找判定数中的结点都是查找成功的情况，将每个结点的空指针指向⼀个实际上不存在的结点——外结点，所有外界点都是查找不成功的情况，如图所⽰。
算法设计与分析各种查找算法的性能测试目录摘要 (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 算法背景查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。
对于查找问题来说，没有一种算法在任何情况下是都是最优的。
有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。
实现顺序查找和折半查找的算法顺序查找和折半查找（也称为二分查找）是两种常见的查找算法。
以下是它们的Python实现：1. 顺序查找：```pythondef sequential_search(list, item):pos = 0found = Falsewhile pos < len(list) and not found:if list[pos] == item:found = Trueelse:pos = pos+1return found```这个函数会检查列表中的每个元素，直到找到匹配的元素或者遍历完整个列表。
如果找到匹配的元素，函数会返回True，否则返回False。
2. 折半查找：```pythondef binary_search(list, item):low = 0high = len(list) - 1mid = 0found = Falsewhile low <= high and not found:mid = (high + low) // 2if list[mid] == item:found = Trueelif list[mid] < item:low = mid + 1else:high = mid - 1return found```这个函数使用二分查找算法，每次比较列表中间的元素和目标元素。
如果中间元素等于目标元素，函数返回True。
如果中间元素小于目标元素，函数在列表的右半部分继续查找。
如果中间元素大于目标元素，函数在列表的左半部分继续查找。
如果函数遍历完整个列表都没有找到目标元素，那么返回False。
第三次实验报告：几种查找算法的实现和比较//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;}}*/}。
顺序查找与二分查找对比近年来，随着信息技术的迅猛发展，各行各业对于数据的处理和检索需求越来越大。
其中，查找是一种常见并且重要的操作。
在众多查找算法中，顺序查找和二分查找是两种常见的方法。
本文将对这两种查找算法进行对比，并探讨它们在实际应用中的优劣势。
一、顺序查找顺序查找，又称线性查找，是一种简单直观的查找方式。
它的基本思想是逐个比对待查找元素和列表中的元素，直到找到匹配的元素或遍历完整个列表。
顺序查找的实现相对简单，只需要从列表的第一个元素开始逐个比对即可。
然而，顺序查找的缺点也是很明显的。
随着待查找元素数量的增加，顺序查找的时间复杂度由O(1)线性增长至O(n)，其中n为待查找元素的个数。
这意味着当数据量较大时，顺序查找的效率将大幅下降。
尤其是对于有序列表，顺序查找无法充分利用列表的有序性，在查找效率上存在明显的不足。
二、二分查找二分查找，又称折半查找，是一种高效的有序查找算法。
它利用了有序列表的特性，通过比较待查找元素与有序列表中间位置元素的大小关系，来确定待查找元素可能存在的区间，从而迅速缩小查找范围。
基于这个思想，二分查找可以将查找的时间复杂度从O(n)降低到O(log₂(n))，其中n为列表中元素的个数。
相比于顺序查找，二分查找的优势主要体现在高效性和适用范围上。
对于大规模有序列表，二分查找能够迅速定位目标元素，大大减少了查找的时间成本。
此外，在对近乎有序或近似有序列表进行查找时，二分查找仍能有较好的表现。
然而，二分查找也有其限制之处，它要求列表必须是有序的，这就增加了排序的前置操作，并且仅适用于静态列表，即在查找过程中列表不发生变化。
三、实际应用中的对比在实际应用中，选择合适的查找算法需要考虑到数据规模、数据的有序性以及查找的频率等因素。
下面针对不同场景进行对比：1. 对于小规模或基本有序的数据集合，顺序查找往往是一个简单而直接的选择。
顺序查找代码简单，易于实现，并且不要求待查找元素有序，适用于轻量级的查找操作。
二分查找二分查找算法基本思想二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止.用伪代码来表示, 二分查找算法大致是这个样子的:left = 0, right = n -1while (left <= right)mid = (left + right) / 2casex[mid] < t: left = mid + 1;x[mid] = t: p = mid; break;x[mid] > t: right = mid -1;return -1;第一个正确的程序根据前面给出的算法思想和伪代码, 我们给出第一个正确的程序,但是,它还有一些小的问题,后面会讲到int search(int array[], int n, int v){int left, right, middle;left = 0, right = n - 1;while (left <= right){middle = (left + right) / 2;if (array[middle] > v){right = middle;}else if (array[middle] < v){left = middle;}else{return middle;}}return -1;}下面,讲讲在编写二分查找算法时可能出现的一些问题.边界错误造成的问题二分查找算法的边界,一般来说分两种情况,一种是左闭右开区间,类似于[left, right),一种是左闭右闭区间,类似于[left, right].需要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误.比如下面就是错误的二分查找算法:int search_bad(int array[], int n, int v){int left, right, middle;left = 0, right = n;while (left < right){middle = (left + right) / 2;if (array[middle] > v){right = middle - 1;}else if (array[middle] < v){left = middle + 1;}else{return middle;}}return -1;}这个算法的错误在于, 在循环初始化的时候,初始化right=n,也就是采用的是左闭右开区间,而当满足array[middle] > v的条件是, v如果存在的话应该在[left, middle)区间中,但是这里却把right赋值为middle - 1了,这样,如果恰巧middle-1就是查找的元素,那么就会找不到这个元素.下面给出两个算法, 分别是正确的左闭右闭和左闭右开区间算法,可以与上面的进行比较: （下面这两个算法是正确的）int search2(int array[], int n, int v){int left, right, middle;left = 0, right = n - 1;while (left <= right){middle = (left + right) / 2;if (array[middle] > v){right = middle - 1;}else if (array[middle] < v){left = middle + 1;}else{return middle;}}return -1;}int search3(int array[], int n, int v){int left, right, middle;left = 0, right = n;while (left < right){middle = (left + right) / 2;if (array[middle] > v){right = middle;}else if (array[middle] < v){left = middle + 1;}else{return middle;}}return -1;}死循环上面的情况还只是把边界的其中一个写错, 也就是右边的边界值写错, 如果两者同时都写错的话,可能会造成死循环,比如下面的这个程序:int search_bad2(int array[], int n, int v){int left, right, middle;left = 0, right = n - 1;while (left <= right){middle = (left + right) / 2;if (array[middle] > v){right = middle;}else if (array[middle] < v){left = middle;}else{return middle;}}return -1;}这个程序采用的是左闭右闭的区间.但是,当array[middle] > v的时候,那么下一次查找的区间应该为[middle + 1, right], 而这里变成了[middle, right];当array[middle] < v的时候,那么下一次查找的区间应该为[left, middle - 1], 而这里变成了[left, middle].两个边界的选择都出现了问题, 因此,有可能出现某次查找时始终在这两个范围中轮换,造成了程序的死循环.溢出前面解决了边界选择时可能出现的问题, 下面来解决另一个问题,其实这个问题严格的说不属于算法问题,不过我注意到很多地方都没有提到,我觉得还是提一下比较好.在循环体内,计算中间位置的时候,使用的是这个表达式:middle = (left + right) / 2;假如,left与right之和超过了所在类型的表示范围的话,那么middle就不会得到正确的值. 所以,更稳妥的做法应该是这样的:middle = left + (right - left) / 2;更完善的算法前面我们说了,给出的第一个算法是一个"正确"的程序, 但是还有一些小的问题.首先, 如果序列中有多个相同的元素时,查找的时候不见得每次都会返回第一个元素的位置, 比如考虑一种极端情况:序列中都只有一个相同的元素,那么去查找这个元素时,显然返回的是中间元素的位置.其次, 前面给出的算法中,每次循环体中都有三次情况,两次比较,有没有办法减少比较的数量进一步的优化程序?<<编程珠玑>>中给出了解决这两个问题的算法,结合前面提到溢出问题我对middle的计算也做了修改:int search4(int array[], int n, int v){int left, right, middle;left = -1, right = n;while (left + 1 != right)//这个循环维持的条件是left<right && array[left]<v<=array[right],所以到最后的时候，{//如果可以找到目标，则只剩下两个数，并且满足 array[left]<v<=array[right],是要查找的数是rightmiddle = left + （right －left) / 2;if (array[middle] < v)//必须保证array[left]<v<=array[right]，所以left = middle;{//如果left =middle+1,则有可能出现array[left]<=v的情况left = middle;}else{right = middle;}}if (right >= n || array[right] != v){right = -1;}return right;}这个算法是所有这里给出的算法中最完善的一个,正确,精确且效率高.但是这个算法的还是不能很好的理解可以用下面的算法，可以找出满足条件的数[cpp]view plaincopy1.int Bi_Search(int a[],int n,int b)//2.{//返回等于b的第一个3.if(n==0)4.return -1;5.int low = 0;6.int high = n-1;7.int last = -1;//用last记录上一次满足条件的下标8.while (low<=high)9. {10.int mid = low +(high-low)/2;11.if (a[mid]==b)12. {13. last = mid;14. high = mid -1;15. }16.else if(a[mid]>b)17. high = mid -1;18.else19. low = mid +1;20. }21.22.return last;23.24.}25.int Bi_Search1(int a[],int n,int b)//大于b的第一个数26.{27.if(n<=0)28.return -1;29.int last = -1;30.int low = 0;31.int high = n-1;32.while (low<=high)33. {34.int mid = low +(high - low)/2;35.if(a[mid]>b)36. {37. last = mid;38. high = mid -1;39. }40.else if (a[mid]<=b)41. {42. low =mid +1;43. }44. }45.46.return last;47.}查找（二）：二分查找一、二分查找(Binary Search)二分查找又称折半查找，它是一种效率较高的查找方法。
Java中常用的查找算法——顺序查找和二分查找一、顺序查找：a)原理：顺序查找就是按顺序从头到尾依次往下查找，找到数据，则提前结束查找，找不到便一直查找下去，直到数据最后一位。
b)图例说明：原始数据：int[] a={4,6,2,8,1,9,0,3};要查找数字：8代码演示：import java.util.Scanner;/** 顺序查找*/public class SequelSearch {public static void main(String[] arg) {int[] a={4,6,2,8,1,9,0,3};Scanner input=new Scanner(System.in);System.out.println("请输入你要查找的数：");//存放控制台输入的语句int num=input.nextInt();//调用searc()方法，将返回值保存在result中int result=search(a, num);if(result==-1){System.out.println("你输入的数不存在与数组中。
");}elseSystem.out.println("你输入的数字存在，在数组中的位置是第："+(result+1)+"个");}public static int search(int[] a, int num) {for(int i = 0; i < a.length; i++) {if(a[i] == num){//如果数据存在return i;//返回数据所在的下标，也就是位置}}return -1;//不存在的话返回-1}}运行截图：二、二分查找a)前提条件：已排序的数组中查找b)二分查找的基本思想是：首先确定该查找区间的中间点位置：int mid = (low+upper)/ 2；然后将待查找的值与中间点位置的值比较：若相等，则查找成功并返回此位置。
上机实验报告实验课题：实现对有序数据集合的顺序查找和二分查找，并展示出查找过程设计思路：我们可以采用数组有序的保存所有数据，这样便于将数据的有序性和其索引的有序性统一起来，同时也便于查找数据。
需要声明的是，我们不使用零下标的项，这样做是为了在顺序查找中优化传统顺序查找算法，具体原因后面会有详细介绍。
为此，我们可以设计一个类，私有变量声明为该数组和数组的长度。
由于集合中的数据类型未知，所以该类为模板类。
对于公有成员，我们创建六个成员函数，除了构造函数和析构函数，其他四个函数分别用来获取外界传入的数组长度、获取外界传入的数组数据、对数据实现顺序查找、对数据实现二分查找。
这里，我们只重点介绍顺序查找函数和二分查找函数。
对于顺序查找，我们对传统的顺序查找方法进行优化，避开每次对数据索引是否越界进行判断这一步骤。
具体做法是：将所查找的元素保存在零下标的项中(这也是零下标闲置的原因)，然后按照下标顺序从后向前依次遍历匹配所查找元素与数组元素。
若两者相等，展示出该数组元素，并将其下标值反馈给客户；若两者不相等，展示出该元素，进行下一轮匹配。
若最终标记下标达到零下标处，说明未查找到所要查找的元素，则客户反馈该信息。
优化后的顺序查找算法比传统的顺序查找算法减少一半的步骤，原因在于每次无须判断标记下标是否越界，这是该算法优化后的优点。
它的缺点是没有利用到数据集合有序这一性质，且查找效率低。
对于二分查找，我们声明三个整型变量low、high和mid 依次标记查找域的上界下标、下界下标和中值下标，其中mid=(low+high)/2。
我们在开始的时候将low初始化为1(上文中提到过，我们是从下表为1的位置开始存储数据)，将high初始化为len(数组长度)，并由此初始化mid的值。
对于任意一次查找，将索引为mid的值与所查找的值进行比较。
若两者相等，则将该元素的索引值反馈给客户；若所查找的值比索引为mid的值小，则将high的值变为mid-1，进行下一轮的查找；若所查找的值比索引为mid的值大，则将low 的值变为mid+1，进行下一轮查找。
若最终low>high，则表明未查找到所要查找的值，将此信息反馈给客户。
该算法是一种效率很高的算法，因为它充分利用到数据集合的有序性，这一优点在数据规模较大时体现的更明显。
实验过程分析：1.在编码过程中，出现了诸如语句末尾逗号遗漏等低级错误。
2.在对WL类的成员函数编码时，出现了函数声明错误，原因是对模板类的语法不熟，编码较少，对类面向对象这一思想理解不透彻。
3.在编码用户选择菜单等地方时，考虑到了程序的健壮性，添加了异常处理，比以前进步。
源代码：#include <iostream>#include "WL.h"#define MAX 10000 //定义数组的最大长度using namespace std;int main(){WL<int> p; //以整形数据为例，将模板类实例化int num,i,x; //num用来存储数组长度，x存储所查找的值int a[MAX];char s;cout<<"Please input the length of the array:"; //提示用户输入数组长度cin>>num;p.getlen(num);cout<<"Please input each data in order:"; //提示用户依次输入数据，并将其保存在数组中for(i=1;i<=num;i++)cin>>a[i];p.getdata(a,num);cout<<endl;cout<<"Please input the data searched:"; //提示用户输入所查找的值cin>>x;cout<<endl;loop:cout<<"Please choose the way for search:"<<endl; //提示用户选择查找方式，并进行查找cout<<"1. Order_search"<<endl;cout<<"2. Binary_search"<<endl<<endl;cout<<"Please input the figure notation:";cin>>s;cout<<endl;if(s=='1')p.find(x);else if(s=='2')p.binary_search(x);else{cout<<"Operator error!"<<endl<<endl; //若用户输入值不为‘1’或‘2’，对用户进行提示重新操作goto loop;}return 0;}***********************************************#ifndef WL_H_INCLUDED#define WL_H_INCLUDED#include <iostream>#define MAX 10000using namespace std;template <class T> //由于数据类型未知，采用模板类声明class WL{private:T s[MAX]; //对存储数据的数组进行声明int len; //对数组长度进行声明public:WL() {};~WL() {}void getlen(int num); //从外界获取数组长度值，并将其传给lenvoid getdata(T a[],int num); //从外界获取数组数据，并将其传给s[MAX] void find(const T x); //顺序查找函数声明void binary_search(const T x); //二分查找函数声明};template <class T>void WL<T>::getlen(int num){len=num;}template <class T>void WL<T>::getdata(T a[],int num){int i;for(i=1;i<=num;i++)s[i]=a[i];}template <class T>void WL<T>::find(const T x){int i=len; //将标记下标初始化为lens[0]=x; //将所查找元素赋给s[0]cout<<"The process of the search:";while(s[i]!=x) //若未查找到x，展示出该数据值{cout<<s[i]<<' ';i--;}if(i)cout<<s[i];cout<<endl;if(!i) //若i=0，说明查找失败，将该信息反馈给客户cout<<"Sorry,no result!"<<endl;else //若i！=0，将索引值反馈给客户cout<<"The index of the data is "<<i<<endl;}template <class T>void WL<T>::binary_search(const T x){int low=1,high=len; //声明并初始化low、highint mid;cout<<"The process of the search:";while(low<=high) //low<=high 说明还未找到所查找的值{mid=(low+high)/2;if(x==s[mid]) //若找到所查找的元素，将该值展示出来，并将索引值反馈给客户{cout<<s[mid]<<endl;cout<<"The index of the data is "<<mid<<endl;return;}else if(x<s[mid]) //若x比s[mid]小，将查找域上界变为mid-1{cout<<s[mid]<<' ';high=mid-1;}else //若x比s[mid]大，将查找域下界变为mid+1{cout<<s[mid]<<' ';low=mid+1;}}cout<<endl;cout<<"Sorry,no result!"<<endl; //若low>high，说明查找失败，将信息反馈给客户}#endif // WL_H_INCLUDED测试结果：顺序查找：二分查找：。
