優(yōu)缺點
二分查找又稱折半查找屑宠。
- 優(yōu)點：比較次數(shù)少妒挎，查找速度快，平均性能好西饵。
- 缺點：要求待查表為有序表酝掩，且插入刪除困難。
因此眷柔，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表期虾。
舉個例子
首先原朝，假設(shè)表中元素是按升序排列，
- 將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較镶苞，如果兩者相等喳坠，則查找成功；
- 否則利用中間位置記錄將表分成前茂蚓、后兩個子表壕鹉，
如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表聋涨，
否則進(jìn)一步查找后一子表晾浴。重復(fù)以上過程，直到找到滿足條件的記錄使查找成功牍白，或直到子表不存在為止脊凰，此時查找不成功
算法復(fù)雜度
二分查找的基本思想是將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.
時間復(fù)雜度無非就是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ù)）
所以時間復(fù)雜度可以表示O()=O(logn)
偽代碼
下面提供一段二分查找實現(xiàn)的[偽代碼]
int BinSearch(SeqList *R仑性，int n,KeyType K)
{
//在有序表R[0..n-1]中進(jìn)行二分查找惶楼，成功時返回結(jié)點的位置，失敗時返回-1
int low=0,high=n-1,mid诊杆；//置當(dāng)前查找區(qū)間上歼捐、下界的初值
while(low<=high)
{
if(R[low].key==K)
return low;
if(R[high].key==k)
return high; //當(dāng)前查找區(qū)間R[low..high]非空
mid=low+((high-low)/2)；
/*使用(low+high)/2會有整數(shù)溢出的問題
（問題會出現(xiàn)在當(dāng)low+high的結(jié)果大于表達(dá)式結(jié)果類型所能表示的最大值時晨汹，
這樣豹储，產(chǎn)生溢出后再/2是不會產(chǎn)生正確結(jié)果的，而low+((high-low)/2)
不存在這個問題*/
if(R[mid].key==K)
return mid淘这；//查找成功返回
if(R[mid].key<K)
low=mid+1剥扣；//繼續(xù)在R[mid+1..high]中查找
else
high=mid-1;//繼續(xù)在R[low..mid-1]中查找
}
if(low>high)
return -1铝穷；//當(dāng)low>high時表示所查找區(qū)間內(nèi)沒有結(jié)果钠怯，查找失敗
}
