Binary search - daya daga cikin mafi sauki hanyoyin samun wani kashi a cikin wani tsararru

Popular sau da yawa, shirye-shirye, ko da sabon shiga, da fuskantar da cewa akwai wani sa na lambobi, wanda dole ne samu takamaiman adadin. Yana da wannan tarin aka kira wani tsararru. Kuma a sami abubuwa a cikinsa, akwai wani kuma ɗimbin hanyoyi. Amma mafi sauki daga gare su, za a iya daukan wani binary search on dama. Menene wannan hanya ne? Kuma da yadda za a yi binary search? Pascal ne mafi sauki yanayi domin kungiyar na da irin wannan shirin, don haka za mu yi amfani da shi ya yi karatu.

Da farko, bincika, abin da suke da abũbuwan amfãni daga wannan hanya, shi ne don haka za mu iya fahimtar, abin da yake da ɗan lokaci, a binciken da topic. Saboda haka, bari mu yi wani tsararru tare da wani girma na akalla 100000000 abubuwa, wanda bukatar a sami wasu. Hakika, wannan matsala za a iya warware ta sauƙi mai sauki mikakke search, a cikin abin da muke amfani da zagayowar zai kwatanta bukata kashi tare da dukan waɗanda suke a cikin tsararru. Matsalar ita ce, da aiwatar da wannan ra'ayin za su dauki lokaci da yawa. A wani sauki Pascal shirin zuwa dama jiyya, da kuma uku Lines daga cikin manyan rubutu, za ka ba lura da shi, amma a lokacin da muka zo da wani fiye ko žasa da manyan ayyukan da manyan yawan rassan da kyau aiki, da shirin zai kasance a shirye da za a ɗora Kwatancen ga tsayi da yawa. Musamman idan kwamfutar ne mai rauni yi. Saboda haka, akwai wani binary search, wanda rage search lokaci a kalla sau biyu.

Saboda haka, abin da yake aiki manufa da wannan hanyar? Nan da nan ya ce: cewa binary search aiki ne ba a wani tsararru, amma kawai a kan wani An ware sa na lambobin. A kowane mataki dauka tsakiya kashi na tsararru (ma'ana yawan kashi). Idan bukata lambar ne mafi girma daga cikin talakawan, to, duk da cewa an bar, cewa shi ne kasa fiye da talakawan cell, za a iya jefar da kuma ba su duba can. Conversely, idan kasa da matsakaita - daga cikin wadanda lambobi zuwa dama, za ka iya ba bincika. Sa'an nan zaɓi sabon search yankin, inda da farko rabi zai zama tsakiyar kashi na gaba tsararru, kuma na karshe da kuma na karshe nufin. A talakawan yawan sabon filin zai zama ¼ na duk rabi, cewa shi ne, (na karshe kashi + tsakiyar kashi na gaba tsararru) / 2. Sake, wannan aiki aka yi - a kwatanta da talakawan yawan da tsararru. Idan manufa darajar ne kasa da matsakaita, mun kãfirta da gefen dama, da kuma yin gaba, har yanzu wannan tsakiya kashi ba za a so.

Hakika, shi ne mafi kyau a dubi wani misali na yadda za a rubuta binary search. Pascal nan zai dace kowa - version ne ba muhimmanci. Bari mu rubuta wani sauki shirin.

Yana da wani sashi na 1 zuwa h karkashin sunan "massiv", wani m nuna ƙananan iyaka da search, da ake kira "niz", na sama da iyaka, da ake kira "verh", da talakawan search lokaci - "sredn". da ake bukata da dama - "isk".

Saboda haka, da farko za mu sanya manya da ƙananan iyakar zangon search:

niz: = 1;
verh: = h + 1.

Sa'an nan tsara da sake zagayowar "har kasa ne kasa da na sama da iyaka":

Duk da yake niz fara

A kowane mataki, mu raba kashi 2:

sredn: = (niz + verh) rara 2; {Amfani da aiki rara, saboda raba ba tare da ragowa}

Kowane lokaci na nazari. Saboda abu an riga an samu idan matsakaici ne ake so, soke sake zagayowar:

іf sredn = isk sa'an nan karya.

Idan tsakiyar kashi na tsararru fiye da so, jefar da gefen hagu, da cewa shi ne, da babba iyaka da talakawan sanya kashi:

idan massiv [sredn]> isk sa'an nan verh: = sredn.

Kuma idan akasin haka, shi ya sa ƙananan iyaka:

kuma niz: = sredn.
ƙare.

Wannan duk da cewa za ta kasance a cikin shirin.

Bari mu bincika yadda zai duba da binary Hanyar in yi. Ka yi la'akari da wannan tsararru: 1, 3, 5, 7, 10, 12, 18 da kuma shi za su nemi lambar 12.

A cikin duka da muke da 7 abubuwa, don haka za ta huɗu matsakaici, da darajar 7.

Tun fiye da 12, 7, 1.3 da kuma 5 abubuwa, za mu iya jefar. Sa'an nan mun samu lambar 4, 4/2 ba saura ne 2. Saboda haka, wani sabon kashi zai zama wani talakawan na 10.

Tun da 12 ne mafi girma daga 10, mun jefar 7. zauna kawai 10, 12 da kuma 18.

A nan, tsakiyar kashi ne riga 12, shi ne ake bukata da dama. Wannan aiki da aka kammala - lambar 12 samu.