折半查找法是效率较高的一种查找方法，假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是：
设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找。
否则，若X大于am，替换下限l=m+1，到下半段继续查找。
若X小于am，换上限h=m-1，到上半段继续查找，如此重复前面的过程直到找到或者l>h为止。
如果l>h，说明没有此数，打印找不到信息，程序结束。
该方法是查找的范围不断缩小一半，所以查找效率较高。
扩展资料
折半查找法优缺点
Bentley在自己的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。
问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。
折半查找法的优点是比较次数少，查找速度快，平均性能好。
其缺点是要求待查表为有序表，且插入删除困难，因此折半查找方法适用于不经常变动而查找频繁的有序列表。
参考资料来源：百度百科-折半查找法
温馨提示：答案为网友推荐，仅供参考
第1个回答 2020-01-09
第2个回答 推荐于2017-11-26
通过一次比较，将查找区间缩小一半。折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。算法步骤描述：step1 首先确定整个查找区间的中间位置mid = （ left + right ）/ 2step2 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功若大于，则在后（右）半个区域继续进行折半查找若小于，则在前（左）半个区域继续进行折半查找 Step3 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放。折半查找算法举例 对给定数列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。折半查找的算法讨论：优点: ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。考虑：能否通过一次比较抛弃更多的部分（即经过一次比较，使查找范围缩得更小），以达到提高效率的目的。……？可以考虑把两种方法（顺序查找和折半查找）结合起来，即取顺序查找简单和折半查找高效之所长，来达到提高效率的目的？实际上这就是分块查找的算法思想。例如：[问题分析] 由于数据按升序排列,故用折半查找最快捷. program binsearch;const max=10;var num:array[1..max] of integer;i,n:integer;procedure search(x,a,b:integer);var mid:integer;beginif a=b thenif x=num[a] then writeln('Found:',a) else writeln('Number not found')else beginmid:=(a+b) div 2;if x>num[mid] then search(x,mid,b);if x nCode) {jMax--;} else if(nList[jCur] < nCode) {jMin++;} else if(nList[jCur] == nCode) {nIndex = jCur;break;}jCur = (jMin + jMax)/2;} while(jMin < jMax);return nIndex;}二分查找的性能说明虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费 O(n lg n) 的时间。 二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。 对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找二分查找的C#实现代码：using System;using System.Collections.Generic;using System.Text;namespace BinschDemo{ public class BinschDemo { public static int Binsch(int[] a, int key) { int low = 1; int high = a.Length; while (low <= high) { int mid = (low + high) / 2; if (key == a[mid]) { return mid; //返回找到的索引值 } else { if (key < a[mid]) high = mid - 1; else low = mid + 1; } } return -1; //查找失败 } static void Main(string[] args) { Console.WriteLine("请输入10个递增数字: "); int[] list = new int[10]; for (int i = 0; i < 10; i++) { Console.Write("数字 : ", i); list = Convert.ToInt32(Console.ReadLine()); } Console.Write("请输入一个你要查找的数字:"); int find = Convert.ToInt32(Console.ReadLine()); int result = Binsch(list, find); Console.WriteLine(result); } }}本回答被提问者采纳
相似回答