對分搜尋

對分檢索（粵拼：deoi3 fan1 gim2 sok3；英文：binary search），又叫對分搜尋、二分檢索、折半檢索，係種演算法。電算上來講，喺一列資料裏面，預先排好次序，就用呢個方法，靠序號就好快搵到要嘅資料。呢個方法，係將資料拆一半，收窄範圍，搵唔到再拆一半，直至無晒爲止。搵嘅次數，頂多係項數嘅二進對數。

方法

簡單來講，首先諗定要搵嘅號，然後將一列數分兩半，細序號果邊叫細半，大序號果邊叫大半，分唔勻就細半就多一隻。細半最尾一隻，就當中間。跟住個號對一對中間嘅，啱就搵到，唔岩就比大細。大過中間既話，細半就唔要，搵大半，相反就搵細半。呢半就當新一列，又重覆之前搵法，如此類推。如果去到最尾，得返一隻都唔啱，就係無隻啱。

舉個例。有九個數，順序排如下：

次序	一	二	三	四	五	六	七	八	九
號	十一	十四	十六	廿五	廿八	卅二	卅三	卅七	卅九
啱錯	未	未	未	未	未	未	未	未	未

假如我要搵卅七號出來。九嘅二進對數係三點一七左右，即係一定唔過三次。

開始。九隻對分，分唔勻，細半第一到第五，大半第六到第九。中間係細半最尾一隻，即係第五隻。第五隻係廿八號，唔啱。卅七號大過中間廿八號，一定唔喺細半，搵大半。

次序	一	二	三	四	五	六	七	八	九
號	十一	十四	十六	廿五	廿八	卅二	卅三	卅七	卅九
中定錯	錯	錯	錯	錯	錯	未	未	未	未

一步。家下搵大半，第六到第九，總共四隻，分得勻。細半係第六到第七，大半係第八到第九。中間係細半尾，即係第七隻卅三號，唔啱。卅七號大過卅三，一定唔喺細半，搵大半。

次序	一	二	三	四	五	六	七	八	九
號	十一	十四	十六	廿五	廿八	卅二	卅三	卅七	卅九
中定錯	錯	錯	錯	錯	錯	錯	錯	未	未

二步。家下搵大半，第八到第九。兩隻分勻，細半得第八，大半得第九。中間係細半尾，即係第八，係卅七，中喎。答案係第八隻，總共搵咗兩次。

次序	一	二	三	四	五	六	七	八	九
號	十一	十四	十六	廿五	廿八	卅二	卅三	卅七	卅九
中定錯	錯	錯	錯	錯	錯	錯	錯	中	未

假如搵嘅係卅九，就要搵多輪。卅九號大過中間卅七號，唔係細半，喺大半。

次序	一	二	三	四	五	六	七	八	九
號	十一	十四	十六	廿五	廿八	卅二	卅三	卅七	卅九
中定錯	錯	錯	錯	錯	錯	錯	錯	錯	未

三步。大半得第九，單一隻，分唔勻。細半得第九，大半無嘢。中間係細半尾，即係第九，係卅九，中喎。答案係九隻，總共搵咗三次。

次序	一	二	三	四	五	六	七	八	九
號	十一	十四	十六	廿五	廿八	卅二	卅三	卅七	卅九
中定錯	錯	錯	錯	錯	錯	錯	錯	錯	中

假如搵嘅係卅八，咁又點呢。卅八號大過中間卅七號，唔喺細半，喺大半。

三步就變成咁。大半得第九，單一隻，分唔勻。細半得第九，大半無嘢。中間係細半尾，即係第九，係卅九，唔中。因爲得返一隻，唔啱就無。即係搵唔到，完。就算無都好，搵咗三次就完。

次序	一	二	三	四	五	六	七	八	九
號	十一	十四	十六	廿五	廿八	卅二	卅三	卅七	卅九
中定錯	錯	錯	錯	錯	錯	錯	錯	錯	錯

對分搜尋

方法

睇埋