折半查找法
效率高的查找方法
折半查找法是效率較高的一種查找方法。假設有已經按照從小到大的順序排列好的五個整數a0~a4，要查找的數是X，其基本思想是：設查找數據的範圍下限為l=1，上限為h=5，求中點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。
int main()
{
int s[10]={0,1,2,3,4,5,6,7,9,10};
int key=8,left=0,right=9,mid;
while(left<=right)
{
mid=(left+right)/2;
if(key==s[mid]) {printf("%d\n",s[mid]);break;}
else if(key>s[mid]) left=mid+1;
else right=mid-1;
}
system("pause");
return 0;
}
2、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;
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;
}