Qidiruv algoritmlari: chiziqli va binar qidiruv. Hesh-jadval va funksiyani tuzish

log₂n↑
Bu yerda, n -qadamlar soni, ↑ - yaxlidlanganda kata tomonga o’tish
Har bir qadamni tekshirish formulasi
mid = (left - right)/2
Agar qiridilayotgan elementning qiymati midga teng bo’lsa, qidiruv yakunlanadi.





Massivga chap va o’ng chegaralarini belgilab olamiz left = 0, right = 19 1-va oxirgi indeks son qiymatini qo’shib 2 ga bo’lamiz mid = (19+0)/2=9. Agar qidirilayotgan element markaziy indeks elementidan katta bo’lsa 69 < 82 qidiruv o’ng tomonga ko’chiriladi va
left = mid = 9
Matritsaning o’ng tomonida markaziy indeksga mos element topiladi mid = (9+19)/2=14 va qidirilayot gan elamaent bilan solishtiriladi:L
84 > 82
Bo’lganligi sababli right = mid = 14
9 va 14 indekslar bo’yicha markaziy indeksga mos elementni topamiz
mid = (9+14)/2=11
11 indeksga mos element qidirilayotgan element bilan solishtiriladi 78 < 82 bo’ladi va left = mid = 11 ga ega bo’lamiz.
11-va 14 indekslar bo’yicha markaziy indeksga mos elementni topamiz
mid = (11+14)/2=12
12-indeksga mos element qiymati qidirilayotgan element bilan solishtiriladi 80 < 82
Va jadvalni o’ng tomonini olamiz
left = mid = 12
12-va 14 indekslar bo’yicha markaziy indeksga mos elementni topamiz
mid = (12+14)/2=13
markaziy indeksga mos elementni qidirilayotgan element bilan solishtiriladi.
82 = 82

Hash haqida

Deyarli ideal xususiyatlarga ega hash daraxtlari tasvirlangan. Ushbu xash daraxtlari boshlang'ichni talab qilmaydi ildiz xesh jadvali hali ham tezroq va zanjirli yoki juft xeshli daraxtlarga qaraganda ancha kam joy ishlatadi. Qo'shish, qidirish va o'chirish vaqtlari kichik va doimiy, kalitlar to'plamining hajmiga bog'liq emas, operatsiyalar O (1). Qo'shish, qidirish va olib tashlash operatsiyalari uchun eng kichik eng yomon vaqtlar kafolatlanishi mumkin va o'tkazib yuborilganlar muvaffaqiyatli qidiruvlarga qaraganda kamroq xarajat qiladi. Massiv xaritalangan urinishlar (AMT), birinchi marta Tez va Space Efficient Trie Searches, Bagwell [2000], asosiy ma'lumotlar strukturasini tashkil qiladi. Kontseptsiya shunday keyin yagona erishadigan algoritmni olish uchun tashqi disk yoki taqsimlangan xotiraga qo'llaniladi kirish qidiruvlari, yagona kirish qo'shimchalariga yaqin va 80 foizdan ortiq disk blokirovkasini yuklash omillari. Linear Hashing, Litwin, Neimat va Schneider [1993] va B-Trees bilan amalga oshiriladi, R.Bayer va E.M.Makkreyt [1972]. Bundan tashqari, AMTlarning yana ikkita qo'llanilishi qisqacha tasvirlangan, ya'ni, Class / Selektor jo'natish jadvallari va IP Marshrutlash jadvallari. Algoritmlarning har biri zamonaviy ilovalar bilan solishtirish mumkin bo'lgan ishlash va makondan foydalanishga ega, ammo oddiyroq. Yaxshi xesh funksiyasini yaratish uchun siz kalitlarning taqsimlanishini bilishingiz kerak. Agar kalit taqsimoti ma'lum bo'lsa, ideal holatda kalit zichligi va xesh qiymatining zichligi taqsimoti bir xil bo'lishi kerak.

1-misol

1. 
   Ketma-ket qidiruv usulidan foydalanib, ro’yxat eng kichik elementini toping?
   

Binar qidiruv orqali qidirish

Ketma ket qidiruv orqali maximalni topish

Bu yerda Samaradorlik elementlar soniga bog’liq agar elementlar soni juda ko’p bo’lsa binar qidiruv optimal variant kamroq bo’lgan vaziyatlarda ketma ket qidiruv yaxshiroq hisoblanadi.

2-misol
Heshlashning “метод свёртки” algoritmi qanday ishlashini tahlil qiling, o’zingizni F.I.SH. ni hesh qiymatini qaytaruvchi dastur tuzing?