Qidiruv usullari: binar qidiruv tafu “Kompyuter injiniring” kafedrasi

Qidiruv usullari: binar qidiruv

TAFU “Kompyuter injiniring” kafedrasi

Salimova Husniya Rustamovna

Amaliy mashg`ulot

• Ishning maqsadi. Talabalarga qidiruv usullari, uning turlari va ko’rinishlarini o‘rgatishdan iborat. Dars jihozi: Shaxsiy kompyuter, videoproyektor, Audiojihozlar, Kolonka, Akustik tizimlar va boshqalar; Kutilayotgan natija: Mavzu yuzasidan bilim, malaka va ko‘nikmaga ega bo‘lish.  

Reja:

1. Binar qidiruv

2. Binar qidirish algoritmi va uning tahlili

3. Masalalar bilan ishlash

Binar qidiruv

• Binar (ikkilik) qidiruv – elementlarning saralangan roʻyxatidan kerakli elementni topish uchun samarali algoritm. Bu usul roʻyxatning siz qidirayotgan element mavjud boʻlgan qismida bitta oʻrin qolmaguncha qismni takroran ikkiga boʻlib boraverish orqali ishlaydi. Biz binar qidiruvni kirish treningidagi taxmin qilish oʻyinida ishlatdik.

• Binar qidiruvni ishlatishning eng keng tarqalgan usullaridan biri massivdan elementni topishdir. Misol uchun, Tycho-2 star katalogida bizning galaktikamizdagi eng yorqin 2 539 913 ta yulduz haqida maʼlumotlar mavjud. Tasavvur qiling, siz biron-bir yulduzni uning nomiga asoslanib katalogdan izlashni xohlayapsiz. Agar dastur chiziqli qidiruv algoritmini qoʻllasa, yaʼni har bitta yulduzni bir boshdan tekshirib chiqsa, unda eng yomon holatda kompyuter 2 539 913 ta yulduzni tekshirishiga toʻgʻri keladi. Agar katalogda yulduz nomlari alifbo boʻyicha tartiblangan boʻlsa, binar qidiruv algoritmi eng yomon holatda ham 22 tadan ortiq yulduzni tekshirishiga toʻgʻri kelmaydi.

Binar qidiruv algoritmi taʼrifi

• Boshqa insonga algoritmni tavsiflab beradigan boʻlsak, koʻpincha toʻliq boʻlmagan taʼrif ham yetarli boʻladi. Masalan, tort retseptida baʼzi, yaʼni tuxumni chiqarish uchun muzlatgichni ochish va tuxumni qanday yorib olish kabi tafsilotlar tushirib qoldirilgan boʻladi. Odamlar tushirib qoldirilgan maʼlumotlarni intuitiv tarzda toʻldirib ketishi mumkin, ammo kompyuter dasturlari bunday qila olmaydi. Shuning uchun biz kompyuter algoritmlarini toʻliq ifodalashimiz kerak.