Maʼlumotlar tuzilmasi va algoritmlarda ikkilik qidirish haqida Ikkilik qidirish

Maʼlumotlar tuzilmasi va algoritmlarda ikkilik qidirish haqida

Ikkilik qidirish — Ο(log n) vaqti murakkabligi bilan tezkor qidiruv algoritmi. Ushbu qidirish algoritmi boʻlinish (divide) va yengish (conque) prinsipi asosida ishlaydi. Ushbu algoritm toʻgʻri ishlashi uchun maʼlumotlar toʻplanishi tartiblangan shaklda boʻlishi kerak.

 

Ikkilik qidirish toʻplamning koʻp qismini oʻrtasini taqqoslash orqali maʼlum bir narsani qidiradi. Agar mos kelsa, unda element indeksi qaytariladi. Agar oʻrta qism elementdan kattaroq boʻlsa, u holda ushbu element oʻrta qismning chap tomonidagi pastki qatorda qidiriladi. Aks holda, element oʻrta elementning pastki qismidagi pastki qatorda qidiriladi. Ushbu jarayon pastki massivda, shuningdek sub-massivning kattaligi nolga tushguncha davom etadi.

 

Ikkilik qidirsh qanday ishlaydi?

Ikkilik qidirish ishlashi uchun maqsad qatorini tartiblash kerak. Ikkilik qidirish jarayonini tasvirli misol yordamida bilib olamiz. Quyidagi tartiblangan massivimiz boʻlib, ikkilik qidirishdan foydalanib, 31 qiymatni qidirish kerakligini taxmin qilaylik.

Birinchidan, ushbu formuladan foydalanib, massivning yarmini aniqlaymiz:

mid = low + (high - low) / 2

Bu yerda, 0 + (9 - 0 ) / 2 = 4 (4.5 ning butun qiymati). Shunday qilib, 4 qatorning oʻrtasida.



Endi biz 4-chi joyda saqlangan qiymatni, yaʼni qidirilayotgan qiymat bilan taqqoslaymiz, yaʼni 31-chi joyda 27-ning qiymati mos kelmasligini aniqladik. Qiymat 27 dan katta boʻlsa va bizda tartiblangan qator mavjud boʻlsa, biz shuni ham bilamizki, maqsad qiymati massivning yuqori qismida boʻlishi kerak.



Biz pastligimizni + 1 oʻrtasiga oʻzgartiramiz va yana yangi oʻrtacha qiymatni topamiz.

low = mid + 1

mid = low + (high - low) / 2

 

Bizning yangi oʻrtamiz endi 7 ga chiqdi. Biz 7-joyda saqlangan qiymatni maqsadli qiymatimiz 31 bilan taqqoslaymiz.

7-joyda saqlangan qiymat mos kelmaydi, aksincha biz qidirayotgan narsadan koʻproqdir. Shunday qilib, qiymat ushbu joyning pastki qismida boʻlishi kerak.



Shunday qilib, biz yana oʻrtani hisoblaymiz. Bu safar 5 ga.

31 maqsadli qiymat 5 manzilda saqlanadi degan xulosaga keldik.

 

Ikkilik qidirish qidiriladigan qismlarni ikki baravar qisqartiradi va shu bilan juda kam sonlar uchun taqqoslash sonini kamaytiradi.

 

Pseudocode

Ikkilik qidirish algoritmlarining kodi quyidagicha koʻrinishi kerak:

Procedure binary_search

A ← sorted array

n ← size of array

x ← value to be searched
Set lowerBound = 1

Set upperBound = n
while x not found

if upperBound < lowerBound

EXIT: x does not exists.



set midPoint = lowerBound + ( upperBound - lowerBound ) / 2



if A[midPoint] < x

set lowerBound = midPoint + 1



if A[midPoint] > x

set upperBound = midPoint - 1
if A[midPoint] = x

EXIT: x found at location midPoint

end while



end procedure