折半查找法

该方法是查找的范围不断缩小一半，所以查找效率较高。

三角形加倍折半法 加倍折半法的关键是如何“加倍”、“折半”。那么“加倍”、“折半”的方法又是什么呢？传统的“加倍”的方法，是将 线段延长一倍；传统的“折半”的方法，是取线段的中点。岂不知，“ 三角形中位线定理”、“ 直角三角形斜边上的中线等于斜边的一半”、“ 等腰三角形的 三线合一性质”、“ 平行线等分线段定理”……均有“加倍、折半”的功用。也就是说“加倍”“折半”的方法是众多的、丰富的。而这些的方法基本上都是来自上述的一些重要的定理。

例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。

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]<key){

low =mid + 1;

}

if(A[mid]>key){

high= mid - 1;

}

}

return -1;

}

#include <stdio.h>int main()

{

int a={0,1,2,3,4,5,6,7,8,9,10},min=0,max=10,mid,n; //max为数列长度，a作为第一个 数组元素

printf("请输入您要查找的数:\n");

scanf("%d",&n);

while(min+1!=max)

{

mid=(min+max)/2;

if (n>a[mid]) min=mid;

else if (n<a[mid]) max=mid;

else

{ printf("输入的数在数列的第%d位\n",mid); break; }

}

if(n==a[max]) printf("输入的数在数列的第%d位\n",max);

else if(n==a[min]) printf("输入的数在数列的第%d位\n",min);

else if(n!=a[mid]) printf("输入的数不在数列中");

return 0;

}

#include <stdio.h>

#include <stdlib.h>

void main()

{

int a={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<a[mid])

bot=mid-1;

}

if(m)

printf("无此数。\n");

system("PAUSE");

return 0;

}