二分查找又稱折半查找血柳，優(yōu)點是比較次數(shù)少，查找速度快生兆，平均性能好难捌；其缺點是要求待查表為有序表，且插入刪除困難鸦难。因此根吁，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。首先合蔽，假設表中元素是按升序排列击敌，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等拴事，則查找成功沃斤；否則利用中間位置記錄將表分成前圣蝎、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字衡瓶，則進一步查找前一子表徘公，否則進一步查找后一子表。重復以上過程哮针，直到找到滿足條件的記錄关面，使查找成功，或直到子表不存在為止诚撵，此時查找不成功缭裆。
二分查找的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較寿烟，如果x=a[n/2],則找到x,算法中止澈驼；如果x<a[n/2],則只要在數(shù)組a的左半部分繼續(xù)搜索x,如果x>a[n/2],則只要在數(shù)組a的右半部搜索x. 時間復雜度無非就是while循環(huán)的次數(shù)！ 總共有n個元素筛武， 漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩余個數(shù)）缝其，其中k就是循環(huán)的次數(shù) 由于你n/2^k取整后>=1 即令n/2^k=1 可得k=log2n,（是以2為底，n的對數(shù)） 所以時間復雜度可以表示O(h)=O(log2n)
來源：百度
