Ikkilik qidirish (Binary search)

“The best place to hide a dead body is the second page of Google search.” — Anonymous

VII bo’lim. Dars 2.

O’tgan darsda chiziqli qidirish algoritmi haqida gaplashgan edik. Oldin ham aytib o’tganimizdek chiziqli qidirish algoritmlari real hayot uchun sekinlik qiladi (bir necha million yozuv orasidan biror yozuvni qidirishni tasavvur qilib ko’ring). Shu sababli, undan ko’ra ancha optimalroq ikkilik qidirish algoritmini ko’rib chiqamiz.
Ikkilik qidirish algoritmi ishlash g’oyasiga ko’ra Bo’lib tashla va hukmronlik qil paradigmasi asosida ishlaydi.

Ikkilik qidirish algoritmi ishlash prinsipi

Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter bilan o’yin o’ynab ko’ramiz. O’yin shartlari quyidagicha:

1. Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish.
2. Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o’ylagan sondan katta yoki kichikligini aytadi.
3. Agar sizning taxminingiz kompyuter o’ylagan son bilan bir xil bo’lsa, o’yin tugaydi.

Xo’sh, bunda kamroq yo’l tutish uchun nima qilgan bo’lar edingiz?

Albatta, birinchi navbatda o’rtadagi sonni taxmin qilib ko’ramiz, ya’ni 50 ni

Aytaylik kompyuter bizga taxminimiz o’ylangan sondan kichikroq ekanligini aytdi. Demak, endi biz 50 va undan kichik barcha son o’ylangan sondan kichik ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar o’rtasidagi sonni olamiz, ya’ni 75 ni

Kompyuter bizga 75 o’ylangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham o’ylangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz o’ylangan sonni topishimiz mumkin.

Sonlar 100 ta bo’lgan holatda, biz har qanday tahminni ko’pi bilan 7 ta qadamda topishimiz mumkin bo’ladi.

Ikkilik qidirish algoritmi ham huddi shunday prinsipda ishlaydi!

Algoritm qadamlari

Algoritm qanday ishlashini tushundingiz degan umiddaman. Endi uning qadamlariga o’tadigan bo’lsak.

Eslatma: Ikkilik qidirish algoritmi to’g’ri ishlashi uchun array saralangan bo’lishi shart!

Bizda n ta elementli saralangan massiv bor va biz undan x elementni qidirmoqdamiz. Biz qidirish chegarasini belgilash uchun l (left) va r (right) ko’rsatkichlardan foydalanamiz. Ular array indekslarini ko’rsatib turadi. mid o’zgaruvchi bizda qidirilayotgan sohaning o’rtadagi elementi indeksini ko’rsatadi

1. Avvaliga l = 0 va r=n-1 bo’ladi (butun boshli array)
2. O’rtadagi element indeksi hisoblanadi: mid = (l + r)/2;
3. O’rtadagi element indeksi bilan qidirilayotgan son x solishtirib ko’riladi
4. Agar son mos kelsa, algoritm shu joyida to’xtaydi.
5. Agar x o’rtadagi sondan katta bo’lsa, left ko’rsatkichni o’rtadan bitta keyingi elementga suramiz: l=mid + 1;
6. Agar x o’rtadagi sondan kichik bo’lsa, right ko’rsatkichni o’rtadan bitta oldingi elementga suramiz: r=mid — 1;
7. 2-qadamga qaytiladi.

Ikkilik qidirish algoritmi har bir qadamda n ni ikki baravarga kamaytirgani uchun algoritm ishlash tezligi O(logn) hisoblanadi.

Algoritm implementatsiyasiga avval o’zingiz mustaqil harakat qilib ko’ring!

Solishtirish uchun Facebook misolidagi 1 mlrd login ichidan ikkilik qidirish algoritmi 30 ta (!) qadam bilan topishi mumkin. Oddiy qidirishdan tashqari bu algoritmni yana boshqa juda ko’p holatlarda ham qo’llash mumkin.

Maqolani sizga yoqqan bo’lsa unga qarsak (clap) chalib qo’yishni esdan chiqarmang. 50 tagacha qarsak chalish mumkin. Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing! Bizning Telegram va YouTube kanallarimizga hamda mening Medium sahifamga obuna bo’ling.

Biz esa uni va ikkilik qidirish turlari implementatsiyasini keyingi video darslarimiz da ko’rib chiqamiz.

Muallif: Qudratxo’ja Musayev

Manba: @AlgorithmUz telegram kanali

YouTube kanalimiz: Algorithms Uzbekistan

“Eng yaxshi reklama — bu mamnun mijoz tomonidan qilingan reklama” — Philip Kotler

Originally published at https://medium.com on April 16, 2019.