Qiduruv tizimlari(Linear Search,Binary Search va boshqalar…)

MUXAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNALOGIYALARI UNIVERSITETI
SAMATQAND FILIALI
KOMPYUTER TIZIMLARI KAFEDRASI
5330500-Kompyuter injiniring talim yo’nalishi
“Taqsimlangan algoritimlar va tizimlar” fanidan
Amaliy topshiriq №1

Mavzu: Qiduruv tizimlari(Linear Search,Binary Search va boshqalar…)

Bajardi : 4-kurs talabasi Saydiyev Vahob.
Qabul qildi : Husanov K.
Samarqand 2022.

Linear Search ­­
Chiziqli qidiruv - ketma-ket qidiruv algoritmi bo'lib, biz bir uchidan boshlaymiz va kerakli element topilgunga qadar ro'yxatning har bir elementini tekshiramiz. Bu eng oddiy qidiruv algoritmidir.
Chiziqli qidiruv qanday ishlaydi?
Quyidagi ro'yxatda k = 1 elementni qidirish uchun quyidagi bosqichlar bajariladi.
Dastur kodi: Python dasturlash muhitida
# Linear Search Python dasturlash muhitida

def linearSearch(massiv, n, x):

for i in range(0, n):

if (massiv[i] == x):
return i
return -1

massiv = [2, 4, 0, 1, 9]

x = 1
n = len(massiv)
result = linearSearch(massiv, n, x)
if(result == -1):
print("Element topilmadi")
else:
print("Element shu indexda topildi: ", result)
Natijasi:

1-dastur natijasi Linear Search algoritmi
Binary search
Ikkilik qidiruv - tartiblangan massivdagi elementning o'rnini topish uchun qidiruv algoritmi.
Ushbu yondashuvda element har doim massiv qismining o'rtasida qidiriladi.
Ikkilik qidiruv faqat elementlarning tartiblangan ro'yxatida amalga oshirilishi mumkin. Agar elementlar hali tartiblanmagan bo'lsa, avval ularni saralashimiz kerak.
Dasturni ikki xil yul bilan yechamiz
1. Iterative Method
Dastur kodi:
# Binary Search python da

def binarySearch(massiv, x, low, high):

# Repeat until the pointers low and high meet each other
while low <= high:

mid = low + (high - low)//2

if massiv[mid] == x:
return mid

elif massiv[mid] < x:

low = mid + 1

else:
high = mid - 1

return -1

massiv = [3, 4, 5, 6, 7, 8, 9]

x = 4

result = binarySearch(massiv, x, 0, len(massiv)-1)

if result != -1:
print("Element mana shu indexda turibdi " + str(result))
else:
print("Topilmadi")