程式介绍
折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数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，说明没有此数，列印找不到信息，程式结束。该方法是查找的範围不断缩小一半，所以查找效率较高。
加倍折半法 的关键是如何“加倍”、“折半”。那么“加倍”、“折半”的方法又是什么呢？传统的“加倍”的方法，是将线段延长一倍；传统的“折半”的方法，是取线段的中点。岂不知，“三角形中位线定理”、“直角三角形斜边上的中线等于斜边的一半”、“等腰三角形的三线合一性质”、“平行线等分线段定理”……均有“加倍、折半”的功用。也就是说“加倍”“折半”的方法是众多的、丰富的。而这些的方法基本上都是来自上述的一些重要的定理。
例1 已知：△ABC中，AB=AC,延长AB到D，使DB=AB，E是AB的中点。求证：CD=2CE
思路一：延长CE到F1，使EF1=CE，即用
延长的方法将CE扩大一倍为CF1，证CF1=CD
思路二：取CD的中点，即用“取中点”的方法将CD缩小一半为CF2，证CF2=CE。
以上为“传统”的加倍折半法，引申后则有：
思路三：抓住E为AB中点这一特点，作△ABF3，使CE为该三角形的中位线（过A作AF3∥CE，交BC的延长线于F3），即用三角形中位线定理将CE扩大一倍为AF3，证AF3=CD
思路四：抓住B为AD中点这一特点，作△ADC以CD边为底边的中位线（过B作BF4∥CD，交AC于F4），即：用三角形中位线定理将CD缩小一半为BF4，证BF4=CE
引申
对三角形加倍折半法“用途”的引申
传统的加倍折半法主要套用于线段（或角）倍半关係的证明。随着“方法”的引申，其功能也随之得到了增强。特别是完全领会了加倍折半法的基本思想后，许多疑难问题就会迎刃而解。它的用途远远超出了原先的範围，几乎适用于所有含“2”的类型题。下面，分“结论中含有2”和“题设中含有2”两中情况作简单的介绍。
1、加倍折半法来解“结论中含有2”的类型题，实际上就是“分析法”的一种具体套用。“加倍折半法”在此起的作用，也可称之为“解题技巧”。例1属于该种类型的“传统”例题，下面举几个引申后的例子。
例2 已知：△ABC中，D是BC上的中点，F是AD上的任意一点，延长CF交AB于E。求证：AF：DF=2AE：BE
思路：本题的难点是如何除去比例式中的“2”
方法一：将AE或DF“加倍”，由于D是BC的中点，
过点B作BG∥DF，交CE的延长线于G，则用三角形中位线定理将DF“扩大一倍”为BG。这样，原题就有效的转化为证明AF：BG=AE：BE。
方法二：是将AF或BE“折半”，由于D是BC的中点，过点D作DH∥AB，交CE于GH，则用三角形中位线的定理将BE“缩小一半”为DH。这样，原题就有效的转化为证明AF：DF=AE：DH。
2、用加倍折半法来解“题设中含有2”的类型题，实际上就是“综合法”的一种具体的套用。“加倍折半法”在此起的作用，可称之为“解题经验”。
例3 已知：△ABC中，AD是高线，∠ABC=2∠ACB。求证：CD=AB+BD
思路：该题属于“截长补短法”的习题，
但由于已知条件中有角的倍半关係，因
而用“加倍折半法”的思路也可以解决。
思路一：延长DB到E1，使BE1=BA（造等腰三角形将∠ABC“折半“为E1），则∠E1=∠C，AE1=AC，CD=DE1，故CD=AB+BD
思路二：作∠CAE2，使∠CAE2=∠C（造等腰三角形将∠C“加倍”为∠AE2B），则∠AE2B=∠ABC，AE2=E2C=AB，BD=DE2，故CD=AB+BD。
优缺点
Bentley在他的着作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜寻算法。问题的关键在于準确地制定各次查找範围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。
折半查找法的优点是比较次数少，查找速度快，平均性能好；
其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
算法步骤描述
① 首先确定整个查找区间的中间位置 mid = （ left + right ）/2 。
② 用待查关键字值与中间位置的关键字值进行比较； 若相等，则查找成功 若大于，则在后（右）半个区域继续进行折半查找 若小于，则在前（左）半个区域继续进行折半查找。
③ 对确定的缩小区域再按折半公式，重複上述步骤。最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构採用一维数组存放。
基本算法实现
函式
bin_search(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;
if(A[mid] low =mid + 1; } if(A[mid]>key){ high= mid - 1; } } return -1; } C语言实现代码 #include { int a[11]={0,1,2,3,4,5,6,7,8,9,10},min=0,max=10,mid,n; //max为数列长度，a[0]作为第一个数组元素 printf(请输入您要查找的数:\n); scanf(%d,&n); while(min+1!=max) { mid=(min+max)/2; if (n>a[mid]) min=mid; else if (n else { printf(输入的数在数列的第%d位\n,mid); exit(0); } } if(n==a[max]) { max+=1; printf(\n输入的数在数列的第%d位\n,max); } else if(n==a[min]) { min+=1; printf(\n输入的数在数列的第%d位\n,min); } else if(n!=a[mid]) printf(\n输入的数不在数列中); } Dev-c++实现 #include #include void main() { int a[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,15}; int n,m,top,bot,mid; top=m=1; //此处修改top=0;m=1; bot=14; printf(please input a number:); scanf(%d,&n); while(top<=bot) { mid=(top+bot)/2; if(n==a[mid]) { printf(这是第%d个元素的值。\n,mid+1); m=0; break; } else if(n>a[mid]) top=mid+1; else if(n bot=mid-1; } if(m) printf(无此数。\n); system(PAUSE); return 0; }
