Dasturlashdagi algoritmlar

Algoritm deb natijaga olib keladigan harakatlar ketma-ketligiga aytiladi. Algoritmning maqsadi turli xil bo‘lishi mumkin: elementlar ro‘yxatini ma’lum bir mezon asosida saralash, minimal yoki maksimal sonni topish va hokazo.

Misol: sho‘rva tayyorlash uchun bir qator ketma-ket harakatlarni bajarish kerak. Masalliqlarni tayyorlash, go‘shtni pishirish, kartoshka, qovurilgan sabzavotlarni qo‘shish, tuzlash va damlab qoʻyish uchun qopqoqni yopish.

Dasturlashda ham xuddi shunday amallar to‘plami mavjud. Vazifasiga ko‘ra ko‘rsatilgan tartibda oxir-oqibat kerakli natijani beradigan aniq amallar to‘plamini bajaramiz. Bu xoh elementlar ro‘yxatini saralash, xoh minimal yoki maksimal elementni topish bo‘lsin.

Massiv nima?

Algoritmlarni chuqurroq bilish uchun dasturlashdagi ma’lumotlar strukturalari qanday tuzilganini tushunish kerak.

Mazkur mavzu “massiv”ning ichki ma’lumotlar strukturasi haqida tushunchaga ega ekaningizni nazarda tutadi. Massivlar bilan tanish bo‘lmagan yoki ularning ishlash tamoyilini batafsil tushunishiga ishonchi komil bo‘lmaganlar uchun rasmli misollar yordamida juda sodda izoh tayyorlaganman:

Buni kinoteatr misolida tushunish osonroq bo‘ladi. Tasavvur qiling, kinoteatrga chipta xarid qilmoqchisiz. Veb-saytga kirasiz va xarid qilish mumkin bo‘lgan oʻrinlarni ko‘rasiz:

Kinoteatrdagi o‘rinlar sxemasi

Misolda 1-qatordagi 1-oʻrinni ko‘rib chiqamiz. Soddalashtirish uchun bu joyni 1x1 deb belgilaymiz.

Ilovadagi xotiraning ham oʻrindiqlari bor, katta, tartibli joy — kinozal ko‘rinishida tasavvur qilish mumkin. Oʻrindiqlarning har bittasi xotira katakchasi deb ataladi. Har bir katakcha kinozaldagi joy kabi o‘z manziliga (bizning misolimizda bu 1x1) ega. Demak, barcha katakchalarning o‘z manzili va qandaydir tartibi bor.

Shuni ham tushunish kerakki, kinozal kabi xotiraning ham chegarasi mavjud. Har bir kinozalda ma’lum miqdordagi o‘rindiqlar boʻladi, toʻgʻrimi? Shunga oʻxshab xotirada ham maʼlum miqdordagi joylar (xotira katakchalari) boʻladi.

Ayrim xotira katakchalari allaqachon boshqa dastur yoki komponentlar tomonidan qandaydir qiymatlar bilan band qilingan bo‘lishi mumkin. Xuddi kinoteatrda boʻlganidek: kinozalga kelganingizda umuman bo‘sh joy qolmagani kabi vaziyat yuzaga keladi. 

Endi tasavvur qilaylik, 5 kishidan iborat guruhingiz kinoteatrga keldi. Hammangiz birga, yonma-yon o‘tirishni xohlashingiz mantiqan to‘g‘ri — bu holda 5 ta chipta sotib olasiz. Uzoq o‘ylab, markazda o‘tirishga qaror qildingiz. Shuning uchun 7-qatorga 5 ta chipta oldingiz:

Kinoteatrda joy sotib olish sxemasi

Kulrang bilan belgilangan kataklar band joylar. Xotiradagi band kataklar kabi.

Birinchi joyni, 7-qatordagi 9-raqamli oʻrindiqni (soddalashtirish uchun buni 9x7 deb belgilaymiz) do‘stingiz Vanya egalladi. Do‘stlar orasida eng oxirgisi Anya bo‘ldi. U 7-qatordagi 13-o‘rindiqqa (buni 13x7 deb belgilaymiz) chipta sotib olgan.

7-qatorda jami 5 ta, 9-dan 13-gacha bo‘lgan o‘rinlarni egalladik. Massivlar ham xuddi shunday tuzilgan: bunday ma’lumotlar strukturasini yaratishda biz n ta ketma-ket xotira katakchalarini (bizning misolimizda o‘rindiqlar soni) zaxiralab qo‘yamiz. Bu yerda n — istalgan manfiy bo‘lmagan butun son (bizning misolimizda bu 5, chunki biz 5 ta joy sotib olganmiz).

Misol tariqasida Java’da kompaniyaning barcha a’zolari uchun chipta raqamlari saqlanadigan qatorlar massivini yaratamiz:

String[] ticketsArray = new String[]{"9x7", "10x7", "11x7", "12x7", "13x7"};

Ba’zi kinoteatrlarda joylarni band qilish imkoniyati mavjud. Chiptalar uchun hali to‘lov qilinmagan boʻlsa-da, bu joylar sizga tegishli ekanini belgilashingiz mumkin. Toʻlovni biroz keyinroq qilasiz, lekin ular allaqachon sizga “tegishli”.

Xotirada ham xuddi shunday: o‘z ehtiyojlarimiz uchun ma’lum miqdordagi katakchalarni band qilib qo‘yishimiz mumkin. Misolimizda kinozaldagi chipta raqamlarini saqlaydigan massiv uchun 5 ta katakchani zaxiralaymiz.

Endi massivlar nima ekanini batafsil ko‘rib chiqa olamiz:

Massiv — oʻzida ma’lum turdagi qiymatlar to‘plamini saqlaydigan ma’lumotlar strukturasi. Massivga har xil turdagi ma’lumotlarni kiritib bo‘lmaydi. Agar massiv String[] sifatida e’lon qilingan bo‘lsa, unda faqat String turiga mansub qiymatlar bo‘lishi mumkin.

Eng muhimi, zaxiralash mexanizmini tushunishdir. Chunki aynan u tufayli biz massiv yaratish imkoniyatiga ega bo‘lamiz. Bu ma’lumotlar strukturasi taqdim etadigan qulayliklardan foydalana olamiz.

Bu esa xuddi misolimizda kinoteatrda guruh uchun joylar band qilinganiga oʻxshaydi. Yaʼni massiv yaratilganda yaqin-atrofdagi xotira katakchalari ham zaxiralanishini anglatadi. Massiv uchun xotiraning turli qismlarida joylashgan 3 ta joyni zaxiralab bo‘lmaydi. Bunday cheklovlar massivlarning afzalligidan foydalanish imkonini beradi. Yaʼni konstanta vaqt ichida indeks orqali elementga kirish imkoniyatini taʼminlaydi.

O‘lchami n = 15 bo‘lgan massivni yaratish va shu tariqa bu massiv uchun xotirani zaxiralash (uni darhol qiymatlar bilan to‘ldirish shart emas) quyidagi usul bilan amalga oshirilishi mumkin:

String[] ticketsArray = new String[15];

Bu vaziyatda xuddi kinoteatrdagi o‘rinlarni band qilganimizdek xotiradagi katakchalarni shunchaki “zaxiralayapmiz”. Balki o‘lchami 15 boʻlgan massivimiz bor-yo‘g‘i 1 ta qiymatga ega bo‘lar. Lekin uning sig‘imi avvalgidek 15 ta elementni tashkil etadi. Shuningdek, uning uchun ajratilgan xotira hech qayerga yo‘qolmaydi. (Bu xuddi to‘yda mehmonlar uchun 15 ta stol ijaraga olingandek gap. Barcha mehmonlarning kelishi noaniq, ba’zi stollar bo‘sh qolishi ham mumkin. Lekin ular baribir to‘yingiz uchun zaxiralangan 15 ta stol bo‘lib qolaveradi :))

Keyingi mavzuga o‘tishimizdan oldin massivlar haqida yana bir necha muhim narsalarni aytib o‘tmoqchiman:

• Massiv indekslarga ega. Bu massivning ma’lum bir elementiga murojaat qilish imkonini beradigan ko‘rsatkichlardir.

• Massiv ichidagi indekslar 0 dan boshlanadi. O‘lchami 5 bo‘lgan massiv yaratilganda birinchi element 0, oxirgisi esa 4 raqami ostida bo‘ladi. (Buni birinchi marta eshitganimda miyam nima sodir bo‘layotganini anglashga urinib, portlab ketay degandi. Lekin ishoning, tez orada siz ham bunga ko‘nikib ketasiz)

• Massiv hajmini oshirib bo‘lmaydi. Ajratiladigan joy statik bo‘lgani sabab massiv uchun joyni e’lon qilish bosqichidayoq ajratamiz. Hajmni oshirish uchun yangi massiv yaratib, unga eski massivdagi ma’lumotlarni ko‘chirish zarur.

  Buni tushunish uchun qator uzunligi 32 ta katakdan iborat katakli daftar varagʻini tasavvur qilish mumkin. 20 katakdan iborat chiziqni kesib olib, unga yana qo‘sholmaymiz. Buning uchun ko‘proq katakdan iborat yangi qatorni kesib olishimiz kerak. Massivlar bilan ham xuddi shunday. Massiv uchun bir marta joy ajratib, faqat shu diapazondan foydalanish mumkin. Yana qo‘shish uchun esa kattaroq o‘lchamli yangi massiv yaratish lozim.

• Massiv uchun ajratilgan joy xotiradagi uzluksiz ma’lumotlar bloki sanaladi. Shu sabab indeks orqali massiv elementini olish konstanta vaqt — O(1) (ya’ni har doim bir xil vaqt ichida) ichida sodir bo‘ladi.

  Tasavvur qiling, 12-xonadonda yashaysiz. Aytaylik, qo‘shningizning xonadoni raqamini bilishingiz kerak boʻlib qoldi. Mantiqan qo‘shningiz xonadonining raqami 13 bo‘lishi kerak. Massivlar ham xuddi shunday ishlaydi. Massivning boshlang‘ich katakchasini bilgan holda belgilangan (konstanta) vaqt ichida massivning kerakli indeksiga murojaat qila olamiz. Kerakli elementga murojaat qilinganida bunday hisoblashni massivning o‘zi bajaradi. Dasturchining faqat kerakli indeks raqamini ko‘rsatishi kifoya!
  

Oxirgi bandni yanada yaxshiroq tushunishingiz uchun batafsil izoh beraman:

Massiv yaratilganda u boshlanish manzilini saqlab qoladi. Agar massivning uchinchi elementini olishimiz kerak bo‘lsa, shunchaki 2-indeksdagi massiv elementiga murojaat qilamiz (hisob 0 dan boshlanishini yodda tutamiz). “Ichkarida” bizga kerakli qiymat yotgan katakning manzili hisoblanadi. Massivning boshlanish manzilini bilgan holda shunchaki bu manzilga + 2 qoʻshib murojaat qilamiz va kerakli elementni olamiz. Unga murojaat qilib, qiymatni olamiz va shu bilan ish bitdi!

Demak, massivning ma’lum bir elementiga murojaat qilish uchun shunchaki indeks bo‘yicha murojaat qilamiz:

String[] ticketsArray = new String[]{"9x7", "10x7", "11x7", "12x7", "13x7"};
System.out.println(ticketsArray[0]);

Oʻrnak sifatida yuqoridagi misoldan foydalandim: faqat birinchi elementning chiqarilishi qo‘shildi. Endi konsolga “9x7” qiymati chiqariladi. Chunki biz massivning 0 raqamli katakchasida boʻlgan birinchi elementga murojaat qildik (yodingizda boʻlsa, massivdagi elementlarni raqamlash 0 dan boshlanardi).

Massivlarni tushunib oldik, endi binar qidiruvga o‘tishimiz mumkin!

Binar qidiruv

Nomidan ko‘rinib turganidek gap qidiruv haqida boradi. Biz unga har yerda — Googleʼning qidiruv satrida so‘rov berganimizda yoki o‘z buyumlarimiz, yon daftarimizda telefon raqamlarini qidirayotganda duch kelamiz.

Xo‘sh, binar qidiruv o‘zi nima?

Binar qidiruv — tartibga solingan to‘plamdagi elementni shu to‘plamni ikkiga bo‘lish orqali izlash usuli.

Endi oddiy so‘zlar bilan tushuntirsak: tartibga solingan (saralangan) qiymatlar ro‘yxati kerakli elementni topgunimizga qadar har safar ikkiga bo‘linadi.

Eng muhimi shuki, binar qidiruv faqat saralangan massivlar uchun amal qiladi!

Endi abstraksiyalanamiz-da, yangi misolni ko‘rib chiqamiz:

Aytaylik, yon daftarimizda biron kishining raqamini topishimiz kerak. Uning familiyasini bilgan holda raqamlarini qisqa vaqt ichida topishimiz mumkin.

Lug‘atda so‘z yoki yondaftarda raqam qidirayotganimizda barcha yozuvlarni ko‘rib chiqmasdan darhol kerakli harfdan boshlaymiz. Shu tariqa kitobning ko‘rib chiqishdan ma’no bo‘lmagan katta qismini chiqarib tashlaymiz.

Faraz qilaylik, bizga kerakli kontaktning familiyasi – “Alekseyev”. Mazkur holatda familiya alifbodagi birinchi harfi bilan boshlangani uchun lug‘atning katta qismini kesib tashlaymiz. Soʻngra familiyaning ikkinchi harfi “l” ekanini koʻramiz va shunga mos ravishda “Al” dan keyingi yoki oldidagi barcha familiyalarni qidiruvdan chiqarib yuboramiz. Shu tarzda davom etib, kerakli kontaktga yetib boramiz. Bunday yondashuv orqali yon daftardagi barcha kontaktlarni koʻrib chiqmaymiz. Balki birma-bir biror qismni chiqarib yuboramiz. Bu esa jarayonni ancha soddalashtirib, qidiruvni tezlashtiradi.

Xuddi shu tarzda 0 dan 100 gacha bo‘lgan diapazonda oʻrin olgan qiymatlar massividagi sonni topishni tasavvur qilishimiz mumkin. Har bir bosqichda (iteratsiyada) 2 ga bo‘lish orqali kerakli sonni topsa boʻladi.

Faraz qilaylik, topilishi kerak boʻlgan son — 65. Sonni o‘ylagan kishi bizning aytgan sonimiz topilishi kerak boʻlgan qiymatdan katta yoki kichik ekanini aytib turadi. Harakatlar tartibi quyidagicha bo‘ladi:

• Massiv o‘rtasiga o‘tamiz, bu – 50 soni. 50 ni topilishi kerak boʻlgan 65 soni bilan taqqoslaymiz. 50 undan kichik, demak, o‘ng tomonga qarab davom etamiz. Shu tariqa dastlabki 50 ta sonni chiqarib tashladik! Natijada iteratsiyalar sonini ikki baravarga qisqartirdik!

• Davom etamiz. Diapazon torayib, 51 dan 100 gacha bo‘lgan sonlarni tashkil qiladi. Bu diapazonning o‘rtasi = (51 + 100) / 2 = 75. 75 soni o‘ylangan sondan kattami? Ha. Demak, 75 dan keyingi sonlarni chiqarib tashlaymiz. Bu harakat bilan mos kelmasligini bilganimiz uchun ko‘rib o‘tirishda ma’no boʻlmagan yana 25 ta sonni chiqarib yubordik!

• Bu bo‘linish sonlar ro‘yxatimiz torayib, massivning o‘rtacha elementi qidirilayotgan songa teng bo‘lgan holatga yetmaguncha davom etadi. Yoki diapazon 1 ta elementga qadar toraymaguncha. Son topildi, bayram qilishimiz mumkin!

Yuqorida tasvirlangan amallar binar qidiruvning mantiqiy mohiyatini tashkil qiladi. Boshqa ma’lumotlar formatlari, masalan, satrlar boʻyicha qidiruv ham xuddi shu tarzda ishlaydi! Agar biz satrlar massividagi kerakli satrni yoki kishi familiyasi bo‘yicha kerakli kontaktni topishimiz kerak bo‘lsa, shunchaki har bir iteratsiyada ro‘yxatning yarmini olib tashlaymiz. Bunday yondashuv massivdagi kerakli elementni O (logN) ta amal yordamida topish imkonini beradi. Bu teskari kvadratga ko‘tarish degani. Ya’ni logarifm darajaga ko‘tarishning teskari amalidir:

Logarifm izohi (A.Bxargava, “Algoritmlar mohiyatini anglash”)

Binar qidiruvni Java’da amalga oshirish

Boshida binar qidiruvni g‘oyaning o‘zini tushungan holda mustaqil ravishda yozganman. Boshim gʻovlab ketib, amalga oshirishda xatolarga yo‘l qo‘yganim uchun bunga taxminan 2 soat vaqt sarflagandim.

leetcodeʼdagi masala shartlari:

O‘sish tartibida saralangan butun sonlar massivi nums va qidiriladigan butun son elementi berilgan. Numsʼda qidiriladigan narsani topish funksiyasini yozing. Agar qidirilayotgan narsa mavjud bo‘lsa, uning indeksini qaytarish kerak. Aks holda -1 qaytarilsin.

Bajarilish murakkabligi O(log n) bo‘lgan algoritm tuzish zarur.

Hozir qanday fikr yuritganim, yoʻl qoʻygan xatolarim va qanday qilib to‘g‘ri qarorga kelganimni bosqichma-bosqich ko‘rib chiqamiz:

1. Sikl. Massivni bo‘lish ko‘p marta takrorlanadigan harakat ekani aniq. Demak, bizga takror bajariladigan (iteratsiyalanadigan) va sharoitga qarab massivning chap yoki o‘ng qismini olib tashlaydigan sikl kerak.

2. O‘zgaruvchilarda element chegaralarini saqlash. Massiv chegaralari (chap va o‘ng qismlari) bilan ishlash maqsadida ular uchun o‘zgaruvchilarni yaratish hamda o‘rta element indeksini saqlash lozim.

3. Salbiy ssenariy. Qidirilayotgan element sonlar massivida mavjud bo‘lmagan holat ham yuz berishi mumkin. Bunday vaziyatda element indeksini emas, balki -1 ni qaytarish lozim.

– Siklni cheklash va ma’lum bir paytda butun massiv bo‘ylab o‘tganimizni, 

– oxirgi elementga yetib borganimizni, 

– lekin u biz qidirayotgan songa teng bo‘lmasa, -1 ni qaytarish kerakligini anglashimiz zarur.

Birinchi qilgan ishim yuqori darajadagi kodni yozdim. U taxminan quyidagicha ko‘rinishga ega edi:

public class Main {
    public static void main(String[] args) {
        int result = search(new int[]{1, 3, 5, 6, 9}, 99);
        System.out.println(result);
    }

    public static int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        int mid = (low + high) / 2;
        while (true) { // cheksiz sikl
            if (target == nums[mid]) { // agar qidirilayotgan son massiv elementining o‘rta qiymatiga teng bo‘lsa, bu element indeksini qaytaramiz
                return mid;
            }
            if (target > nums[mid]) { // agar qidirilayotgan son massivning o‘rta elementidan katta bo‘lsa, diapazonning chap qismini olib tashlaymiz
                low = mid;
                mid = (low + high) / 2; // massivning chap qismini olib tashlaganimizdan so‘ng uning yangi o‘rtasini hisoblaymiz
            } else if (target < nums[mid]) { // agar qidirilayotgan son o‘rtadan kichik bo‘lsa, diapazonning o‘ng qismini olib tashlaymiz
                high = mid;
                mid = (low + high) / 2; // massivning o‘ng qismini olib tashlaganimizdan so‘ng uning yangi o‘rtasini hisoblaymiz
            } else { // element topilmagan taqdirda -1 ni qaytaramiz 
                return -1;
            }
        }
    }
}

Endi massiv bo‘yicha birinchi iteratsiyani ko‘rib chiqamiz:

Men yaratgan shedevr siklning birinchi iteratsiyasi

Ko‘rinib turganidek, bizning maqsadimiz 99-elementning indeksini topish. Faqat bitta muammo bor: bu yerda bunday element mavjud emas. Bunday holatda massiv -1 ni qaytarishi kerak. Kodni ishga tushirganimizda esa... Cheksiz sikl hosil bo‘ladi, Karl!

Keling, buning sababini aniqlaymiz:

1) While shartida true ko‘rsatilgan. Shu sabab kerakli son mavjud bo‘lmagan holda (bizning misolimizda 99 soni sonlar massivi ichida mavjud emas) sikl qayta-qayta takrorlanadi.

2) 15-satrning ikkinchi shartiga kirganimizda 99 elementi haqiqatan ham o‘rtachadan katta bo‘ladi. Keyin siljish sodir bo‘lishi lozim. Agar chap qismni kesib tashlasak, u holda lowʼning qiymati mid +1 ga teng bo‘lishi kerak. Chunki taqqoslagan o‘rtacha elementimiz bizga kerakli sondan kichik bo‘lib chiqdi. Shunga mos ravishda bu o‘rtacha elementdan 1 pozitsiya o‘ngga (mid + 1) sakrab o‘tishimiz kerak. Sxemada bu quyidagicha ko‘rinishda boʻladi:

Algoritmning to‘g‘ri ishlashi

Ammo bu sodir bo‘lmaydi, natijada biz yana siklga kiramiz. Mid = 2 ni olamiz va bu shu tariqa cheksiz davom etaveradi. Massivning o‘rtasi har doim bir xil bo‘lib qolaveradi. Buni qanday tuzatish mumkin? O‘zingiz o‘ylab ko‘ring, yechim esa sizni spoylerda kutmoqda.

Bu kodda quyidagicha ko‘rinishda bo‘ladi:

public static int search(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1;
    int mid = (low + high) / 2;

    while (low <= high) { // chap va o‘ng qismlar kesishganiga qadar iteratsiyalaymiz
        if (target == nums[mid]) {
            return mid;
        }
        if (target > nums[mid]) {
            low = mid + 1; // low chegarasini 1 element o‘ngga siljitamiz
        } else {
            high = mid - 1; // high chegarasini 1 element chapga siljitamiz
        }
        mid = (low + high) / 2; // low va high diapazonlari siljigandan keyin massiv o‘rtasini qaytadan hisoblaymiz
    }

    return -1; // qidirilayotgan son topilmadi
}

Nima o‘zgarganini aniqlaymiz:

1) Biz cheksiz siklni low <= high shartiga o‘zgartirdik. Bu esa tom ma’noda quyidagini anglatadi. Biz massiv bo‘ylab iteratsiyani amalga oshiramiz va ko‘rsatkichlar (low/high) 1-elementni ko‘rsatganiga qadar sonni qidiramiz. Bunday holatda biz butun massivni ko‘rib chiqib, qidirilgan sonni topa olmadik.

2) Sikl bajarilganidan so‘ng -1 ni qaytaramiz. Bu sikl davomida qidirilayotgan qiymat topilmagan holatda roʻy beradi. Aksincha, agar qidirilayotgan qiymat topilsa, 8-qatorda uning joylashuvi haqidagi javob qaytariladi. Return buyrug‘idan keyin search(int[] nums, int target) metodidan butunlay chiqib ketamiz.

3) Biz sikl ichidagi ketma-ketlikni o‘zgartirdik (low va high chegaralari o‘zgarganidan keyin massivning o‘rtasini qayta hisoblash uchun). Chunki massivning o‘rtasini elementlarning bir qismini olib tashlab, low/high chegaralarini qayta hisoblaganimizdan keyin hisoblashimiz kerak.

Hammasi tushunarli bo‘lishi uchun low va high chegaralarining o‘zgarishi qanday sodir bo‘lishini batafsil ko‘rib chiqamiz:

Mid (diapazonning o‘rtasi) pozitsiyadagi qiymat qidirilayotgan qiymatdan kichik bo‘lsa, o‘ngga o‘tamiz. Ya’ni chap qismni olib tashlashimiz kerak. Quyi chegara (low) o‘rta qism bo‘lgan joyga +1 siljiydi. Siklga kirgan paytimiz birinchi qadamda o‘rtani tekshirib ko‘rib, qidirilayotgan narsa mid pozitsiyadagi elementdan katta ekanini aniqlab olgan edik. Shunga ko‘ra midʼni o‘tkazib yuborish va low chegarasini 3-indeksdagi katakchaga o‘tkazishimiz lozim. Aynan shu sababdan low = mid + 1 amalini bajaramiz:

Quyi chegaraning low = mid + 1 siljishi

Xuddi shunday holat mid indeksi ostidagi element (diapazonning o‘rtasi) qidirilayotgan qiymatdan KATTA bo‘lganda ham sodir bo‘ladi. Demak, qidirilayotgan element o‘rtadagi elementdan kichikroq. Biz o‘ng tomonni, shu jumladan, o‘rta elementning oʻzini ham olib tashlashimiz kerak. Buning uchun biz midʼdan keyingi barcha elementlarni, shu jumladan, uning o‘zini ham olib tashlaymiz. Oldingi operatsiyaga o‘xshash, lekin jarayon high = mid - 1 amalga oshiriladi:

Yuqori chegaraning high = mid - 1 siljishi

Optimallashtirish va soddalashtirishdan so‘ng binar qidiruvning yakuniy varianti quyidagicha bo‘ladi:

public class Main {
    public static void main(String[] args) {
        int result = search(new int[]{1, 3, 5, 6, 9}, 99);
        System.out.println(result);
    }

    public static int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (target > nums[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

Umid qilamanki, narsalarni oddiy so‘zlar bilan tushuntirib bera oldim. Agar shu joyigacha o‘qib kelgan bo‘lsangiz, sizga gap yoʻq, ofarin!

Algoritmlarni o‘rganishda davom eting va yangi nashrlarimizni kuzatib boring!

Manba: Бинарный поиск на пальцах