Jinsi ni utafutaji binary dhidi ya mifumo mingine ya utafutaji?
Context:Sorted safu na utafutaji binary ni ufumbuzi ufanisi sana wakati kuingiza na kufuta shughuli ni interleaved na retrieval, kuchukua  O ((() wakati kwa kila operesheni hiyo. Aidha, safu iliyoainishwa inaweza kutatanisha matumizi ya kumbukumbu hasa wakati vipengele mara nyingi huingizwa kwenye safu. Kuna miundo mingine ya data ambayo inasaidia kuingiza na kufuta kwa ufanisi zaidi. Binary search inaweza kutumika kufanya matching halisi na kuweka uanachama (kuamua kama thamani ya lengo ni katika mkusanyiko wa maadili). Kuna miundo ya data kwamba msaada kwa kasi sahihi vinavyolingana na kuweka uanachama. Hata hivyo, tofauti na mifumo mingine ya utafutaji, utafutaji binary inaweza kutumika kwa ufanisi takriban vinavyolingana, kwa kawaida kufanya mechi hizo katika O ((log n) wakati bila kujali aina au muundo wa maadili wenyewe. Aidha, kuna baadhi ya shughuli, kama kutafuta ndogo na kubwa ya kipengele, ambayo yanaweza kufanyika kwa ufanisi juu ya safu iliyowekwa.  Utafutaji Linear:  Linear search ni rahisi search algorithm kwamba checks kila rekodi mpaka anapata thamani ya lengo. Utafutaji wa mstari unaweza kufanywa kwenye orodha iliyounganishwa, ambayo inaruhusu kuingiza na kufuta haraka kuliko safu. Utafutaji binary ni kasi zaidi kuliko utafutaji linear kwa safu iliyowekwa isipokuwa safu ni mfupi, ingawa safu inahitaji kupangwa mapema. Algorithms zote za kuchagua kulingana na kulinganisha vipengele, kama vile kuchagua haraka na kuchanganya kuchagua, zinahitaji angalau O ((nlog n) kulinganisha katika hali mbaya zaidi. Tofauti na utafutaji linear, utafutaji binary inaweza kutumika kwa ufanisi takriban vinavyolingana. Kuna shughuli kama vile kutafuta ndogo na kubwa ya kipengele ambayo inaweza kufanyika kwa ufanisi juu ya safu iliyoainishwa lakini si juu ya safu unsorted.  Miti:  Binary search miti ni searched kwa kutumia algorithm sawa na binary search. Mti wa utafutaji wa binary ni muundo wa data ya mti wa binary ambayo inafanya kazi kulingana na kanuni ya utafutaji wa binary. Rekodi za mti zimepangwa kwa utaratibu uliowekwa, na kila rekodi katika mti inaweza kutafutwa kwa kutumia algorithm sawa na utafutaji wa binary, kuchukua muda wa wastani wa logarithmic. Kuingiza na kufuta pia kuhitaji kwa wastani logarithmic wakati katika binary miti ya utafutaji. Hii inaweza kuwa kwa kasi zaidi kuliko linear wakati kuingizwa na kufuta ya safu iliyoainishwa, na miti binary kuhifadhi uwezo wa kufanya shughuli zote inawezekana juu ya safu iliyoainishwa, ikiwa ni pamoja na mbalimbali na takriban maswali.  Hata hivyo, utafutaji binary ni kawaida ufanisi zaidi kwa ajili ya kutafuta kama miti utafutaji binary uwezekano mkubwa kuwa imperfectly uwiano, na kusababisha kidogo mbaya utendaji kuliko utafutaji binary. Hii hata inatumika kwa miti ya utafutaji wa binary usawa, miti ya utafutaji wa binary ambayo usawa nodes yao wenyewe, kwa sababu mara chache kuzalisha mti na ngazi chache iwezekanavyo. Isipokuwa kwa miti ya utafutaji wa binary yenye usawa, mti unaweza kuwa na usawa usio na usawa na nodes chache za ndani na watoto wawili, na kusababisha muda wa utafutaji wa wastani na mbaya zaidi ukikaribia n comparisons.[e] Binary search miti kuchukua nafasi zaidi kuliko safu iliyoainishwa.  Binary search miti kujitolea kwa haraka kutafuta katika kumbukumbu ya nje kuhifadhiwa katika disks ngumu, kama binary search miti inaweza kuwa ufanisi muundo katika filesystems. B-mti generalizes njia hii ya shirika mti. B-miti ni mara nyingi kutumika kuandaa kuhifadhi muda mrefu kama vile database na filesystems.  Kuweka alama: Kwa utekelezaji wa safu ya ushirika, meza za hash, muundo wa data ambao ramani funguo kwa rekodi kwa kutumia kazi ya hash, kwa ujumla ni haraka kuliko utaftaji wa binary kwenye safu iliyoainishwa ya rekodi. Utekelezaji mwingi wa meza ya hash unahitaji tu wakati wa kudumu wa wastani. Hata hivyo, hashing sio muhimu kwa mechi za takriban, kama vile kuhesabu ufunguo mdogo zaidi, mkubwa zaidi, na karibu, kwani habari pekee iliyotolewa kwenye utaftaji ulioshindwa ni kwamba lengo haliko katika rekodi yoyote. Utafutaji wa binary ni bora kwa mechi hizo, kufanya nao katika muda logarithmic. Utafutaji binary pia inasaidia mechi takriban. Baadhi ya shughuli, kama kutafuta ndogo na kubwa kipengele, inaweza kufanyika kwa ufanisi juu ya safu ya kupangwa lakini si juu ya meza hash.  Kuweka uanachama algorithms: Tatizo kuhusiana na utafutaji ni kuweka uanachama. Algorithm yoyote ambayo hufanya utafutaji, kama utafutaji wa binary, pia inaweza kutumika kwa uanachama wa kuweka. Kuna algorithms nyingine ambayo ni zaidi hasa yanafaa kwa ajili ya kuweka uanachama. Array kidogo ni rahisi, muhimu wakati mbalimbali ya funguo ni mdogo. Ni compactly kuhifadhi mkusanyiko wa bits, na kila kidogo kuwakilisha ufunguo mmoja ndani ya mbalimbali ya funguo. Arrays kidogo ni haraka sana, wanaohitaji tu O(1) wakati. Judy1 aina ya Judy safu hushughulikia funguo 64-bit ufanisi.  Kwa matokeo ya takriban, Bloom filters, mwingine uwezekano data muundo msingi hashing, kuhifadhi seti ya funguo kwa encoding funguo kutumia safu kidogo na kazi nyingi hash. Bloom filters ni mengi zaidi nafasi ya ufanisi kuliko safu kidogo katika kesi nyingi na si polepole sana: na k hash kazi, wanachama maswali zinahitaji tu Wakati mzuri. Hata hivyo, Bloom filters kuteseka kutokana na uongo chanya.  Miundo nyingine data: Kuna miundo ya data ambayo inaweza kuboresha juu ya utafutaji binary katika baadhi ya kesi kwa ajili ya wote kutafuta na shughuli nyingine inapatikana kwa safu ya kupangwa. Kwa mfano, utafutaji, vinavyolingana takriban, na shughuli inapatikana kwa safu iliyoainishwa inaweza kufanywa kwa ufanisi zaidi kuliko utafutaji binary juu ya miundo maalum ya data kama vile van Emde Boas miti, miti fusion, majaribio, na safu kidogo. Hizi miundo maalumu data ni kawaida tu kwa kasi kwa sababu wao kuchukua faida ya mali ya funguo na sifa fulani (kawaida funguo ambazo ni ndogo integers), na hivyo itakuwa wakati au nafasi ya kutumia kwa funguo kwamba kukosa sifa hiyo. Muda mrefu kama funguo inaweza kuamriwa, shughuli hizi zinaweza kufanyika daima angalau ufanisi juu ya safu iliyochaguliwa bila kujali funguo. Baadhi ya miundo, kama vile safu Judy, kutumia mchanganyiko wa mbinu ili kupunguza hii wakati kudumisha ufanisi na uwezo wa kufanya vinavyolingana approximate.
Sorted safu na utafutaji binary ni ufumbuzi ufanisi sana wakati kuingiza na kufuta shughuli ni interleaved na retrieval. Aidha, safu iliyoainishwa inaweza kutatanisha matumizi ya kumbukumbu hasa wakati vipengele mara nyingi huingizwa kwenye safu. Utafutaji binary ni kasi zaidi kuliko utafutaji linear kwa safu iliyowekwa isipokuwa safu ni mfupi, ingawa safu inahitaji kupangwa mapema. Utafutaji binary ni kawaida ufanisi zaidi kwa ajili ya kutafuta kama miti binary utafutaji itakuwa uwezekano mkubwa kuwa na usawa imperfectly, na kusababisha kidogo mbaya utendaji kuliko utafutaji binary. muundo wa data kwamba ramani funguo kwa kumbukumbu kwa kutumia kazi hash, ni kwa ujumla kasi kuliko utafutaji binary juu ya safu ya kupangwa ya kumbukumbu.