對分檢索

出自維基百科,自由嘅百科全書
跳去: 定向搵嘢

對分檢索(英文binary search),又叫二分檢索折半檢索,係種演算法電算上來講,喺一列資料裏面,預先排好次序,就用呢個方法,靠序號就好快搵到要嘅資料。呢個方法,係將資料拆一半,收窄範圍,搵唔到再拆一半,直至無晒爲止。搵嘅次數,頂多係項數嘅二進對數

方法[編輯]

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

舉個例。有九個數,順序排如下:

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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