Algoritm murakkabligi va binary search

~15 daq · C++ · Fayllar, testlar va loyiha

Muammodan boshlaylik

Katalog o‘sganda har safar barcha elementlarni ko‘rish qimmatlashadi. Qidiruv usuli va uning shartlarini o‘rganamiz.

Tushunib olamiz

Chiziqli qidiruv O(n), saralangan diapazondagi binary search esa O(log n) taqqoslash talab qiladi. Lekin saralashning o‘zi odatda O(n log n); faqat bitta qidiruv uchun uni bajarish doim foydali emas. Binary search diapazoni ayni comparator bo‘yicha saralangan bo‘lishi kerak.

Ishlaydigan misol

Misollar C++17 uchun. Kodni UTF-8 formatda main.cpp fayliga saqlang. Har darsdagi dastur mustaqil kompilyatsiya qilinadi.

#include <iostream>
#include <vector>
#include <algorithm>


int main() {
  std::vector<int> sonlar{7, 2, 9, 4};
  std::sort(sonlar.begin(), sonlar.end());
  std::cout << std::boolalpha << std::binary_search(sonlar.begin(), sonlar.end(), 7) << '\n';
  std::cout << std::binary_search(sonlar.begin(), sonlar.end(), 8) << '\n';
}

GCC/Clang: g++ -std=c++17 -Wall -Wextra -pedantic main.cpp -o dastur (yoki clang++), keyin Linux/macOS’da ./dastur, Windows PowerShell’da .\dastur.exe. MSVC Developer terminalida: cl /std:c++17 /EHsc /utf-8 main.cpp, keyin .\main.exe.

Natija va tahlil

true va false chiqadi. Saralangandan keyin bir xil katalogda ko‘p qidiruv bajarish mumkin.

[!WARNING] Saralanmagan ro‘yxatda binary_search natijasiga tayanmang. Comparatorni saralash va qidiruvda bir xil tanlang.

Mustaqil mashq

Bo‘sh vector, bitta qiymat va takroriy qiymatlar bilan qidiruvni tekshiring.

Avval yechimni yopiq holda o‘zingiz yozing. Oddiy qiymat bilan birga chegara holatini ham tekshiring: bo‘sh ma’lumot, nol yoki mos kelmaydigan qiymat dasturingizga qanday ta’sir qilishini kuzating.

Yechim va tekshirish yo‘li

Bo‘sh vectorda false, mavjud bitta elementda true. Takroriy elementlarning bittasi borligini binary_search bildiradi, sonini emas.

Xulosa

Chiziqli qidiruv O(n), saralangan diapazondagi binary search esa O(log n) taqqoslash talab qiladi.

Misolni ko‘chirib ishlatgandan keyin qiymatlarni almashtiring va natijani oldindan taxmin qiling. Kutilgan natija chiqmasa, kompilyator xabari yoki bajarilish xatosini birinchi satridan boshlab o‘qing.

Keyingi dars: Yakuniy loyiha — faylli kitoblar katalogi.

Rasmiy qo‘llanma: Microsoft Learn: zamonaviy C++