Reja: 1 Binar qidiruv

S = log
2
n. 
Masalan, 
n
= 
1024
.
Ketma-ket qidiruvda 
S = 512
, binar qidiruvda 
S
= 
10
. 
Agar katta xajmdagi ma‟lumotlar ichida qidiruv amalga oshirilayotgan bo‟lsa, u holda binar va 
indeksli ketma-ket qidiruvni umumlashtirib olib borish mumkin. Sababi, har ikkala qidiruv ham 
tartiblangan massivda amalga oshiriladi. 
Binar qidirish(Binary_search)O(log n)
Binar qidiruv o‟sish bo‟yicha saralangan massivdan biz qidirgan sonni topishda ishlatiladi. 
Masalan a{1,2,5,8,9,12} berilgan massivdan 9 sonini oddiy qidiruvda ishlash vaqti O(n) bo‟ladi. 
Lekin agar siz binary qidirishni ishlatsangiz ishlash vaqti ancha tezlashadi yani O(log n) bo‟ladi. 
Endi siz bilan binar qidirish algoritmini g‟oyasini ko‟rib chiqamiz. Binary qidirish massivni 
ikkiga bo‟lish orqali qidiradi yani left va right bo‟lgan ikki o‟zgaruvchi olinadi dastlab left=1 va 
right=n bo‟ladi va left va right qo‟shib ikkiga bo‟ladi(middle=(left+right)/2) shunda massiv 
o‟rtasidagi element(middle) topiladi va tekshiriladi shu element biz qidiryotgan elementga 
tengmi agar teng bo‟lsa shu element turgan index javob qilib yuboriladi aks xolda shart 
tekshiriladi biz qidiryotgan element (find) middle elementdan kattami (a[middle]katta bo‟lsa unda biz qidiryotgan elementimiz massivni o‟ng tomonida yani middle+1 va right 
orasida bo‟ladi aks xolda chap tomonida yani 
left va middle-1 orasida bo‟ladi va shu tariqa ikkiga bo‟lib qidirib borilaveradi. Masalan:
a{1,2,5,8,9,12,34} shu massivdan 9 ni qidirib ko‟raylik. Demak 
1
.left=1 va right=7 middle=(left+right)/2=4 a[middle]≠9; topilmadi 
endi shart tekshiramiz a[middle]<9 bajariladi demak 9 o‟ng tomonda demak 
left=middle+1 bo‟ladi right esa o‟zgarmaydi. O‟ng tomonda {9,12,34}
2
.left=5 va right=7 middle=(left+right)/2=6 a[middle]≠9; topilmadi 
endi shart tekshiramiz a[middle]<9 bajarilmayadi demak 9 chap tomonda ekan demak left 
o‟zgarmaydi right esa right=middle-1 bo‟ladi. 

---

3
.left=5 va right=5 middle=(left+right)/2=5 a[middle]=9;topildi demak javob 
middle=5 ekan.
Masalan: . 
qidir 114 a{-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}. Jadvalda ko‟ramiz.
qadam 1(middle element 19<114):
-1 5 6 18 
19
25 46 78 102 114
qadam 2(middle element 78<114):
-1 5 6 18 19 
25 46 
78
102 114
qadam 3(middle element 102<114):
-1 5 6 18 19 25 46 78 
102
114
qadam 4 (middle element 114=114):
-1 5 6 18 19 25 46 78 102
114
Masalan. 
qidir 6 a{-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}
qadam 1 (middle element 19>6):
-1 5 6 18 
19
25 46 78 102 114
qadam 2 (middle element 5<6):
-1 
5
6 18 
19 25 46 78 102 114
qadam 3 (middle element 6=6):
-1 5 
6
18 
19 25 46 78 102 114
Endi realizatsiyani ko‟rib chiqamiz Pascal tilida: 
var 
a:array[1..1000000] of integer; 
n,find,left,right,middle,i:integer; 
begin 
read(n); 
for i:=1 to n do 
read(a[i]); 
read(find); 
left:=1; right:=n; 
while(left<=right)do 
begin 
middle:=trunc((left+right)/2); 
if(a[middle]=find) then 
begin 
write(middle); 
exit; 
end; 
if(a[middle]left:=middle+1 
else 
right:=middle-1; 
end; 
write('Bunday son topilmadi'); 
end. 
Java tilida xam shunday bo‟ladi Lekin Java va C++ tillarida Binary_searchni tayyor funksiyasi 
mavjud shuni javada ko‟rib chiqamiz. 
import
java.util.Arrays;
import
java.util.Scanner;
public
class
SEARCH_BINARY {
public
static
void
main(String[] args) {
Scanner sc = 
new
Scanner(System.
in
);
int
n=sc.nextInt();
int
a[]=
new
int
[n+1];
for
(
int
i = 1; i <=n; i++) {
a[i]=sc.nextInt();
}
int
find=sc.nextInt();
int
index=Arrays.
binarySearch
(a, find);
System.
out
.println(index);
}

---

C++ tilidagi funksiyasi 
int
binarySearch(
int
arr[], 
int
value, 
int
left, 
int
right) {
while
(left <= right) {
int
middle = (left + right) / 2;
if
(arr[middle] == value)
return
middle;
else
if
(arr[middle] > value)
right = middle - 1;
else
left = middle + 1;
}
return
-1;
} 
Binar daraxtlar 
Binar daraxtlar eng ko‟p foydalaniladigan daraxtlar turi xisoblanadi.
Daraxtlarni EXM xotirasida tasvirlanishiga ko‟ra xar bir element to‟rtta maydonga ega 
yozuv xisoblanadi. Mazkur maydonlar qiymati mos ravishda yozuv kaliti bo‟lib, boshqa 
elementlarga murojaatni ifodalaydi, ya‟ni chapga-pastga, o‟nga-pastga va yozuv matniga.
SHuni esda tutish lozimki, daraxt xosil qilinayotganda, otaga nisbatan chap tomondagi 
o‟g‟il qiymati kichik kalitga, o‟ng tomondagi o‟g‟il esa katta qiymatli kalitga ega bo‟ladi. 
Masalan, quyidagi elementlardan binar daraxt quramiz: 50, 46, 61, 48, 29, 55, 79. U quyidagi 
ko‟rinishga ega bo‟ladi: 
Natijada, o‟ng va chap qism daraxtlari bir xil bosqichli tartiblangan binar daraxt xosil 
qildik. Agar daraxtning o‟ng va chap qism daraxtlari bosqichlari farqi birdan kichik bo‟lsa, 
bunday daraxt ideal muvozanatlangan daraxt deyiladi. Yuqorida xosil qilgan binar daraxtimiz 
ideal muvozanatlangan daraxtga misol bo‟ladi. 
Binar daraxtni xosil qilish uchun EXM xotirasida elementlar quyidagi turda bo‟lishi 
lozim: 
V = MakeTree(Key, Rec) amali ikkita ko‟rsatkichli (kalit) va ikkita maydonli (informatsion) 
element yaratadi (daraxt tuguni) 
MakeTree protsedursi ko‟rinishi: 
Paskalь 
New(p); 
p^.r := rec; 
p^.k := key; 
v := p; 
p^.left := nil; 
p^.right := nil; 
Boshida kalit birinchi qiymati kiritiladi. Undan so‟ng elementni o‟zini maketree 
protsedurasi orqali hosil qilamiz. Keyin esa ko‟rsatkich bo‟sh qiymatni ko‟rsatguncha tsiklni 

---

davom ettiramiz. 
READ(key,rec) 
tree=maketree(key,rec) 
WHILE not eof DO 
READ(key,rec) 
V=maketree(key,rec) 
WHILE P<>nil DO 
Q=P 
IF key=k(P) 
THEN P=left(P) 
ELSE P=right(P) 
END IF 
END WHILE 
IF P=nil 
THEN WRITELN(' Bu ildiz'); 
tree=V 
ELSE IF keyTHEN left(P)=V 
ELSE right(P)=V 
END IF 
END IF 
END WHILE 
Tanlash orqali saralash. 
G‟OYA: 
•
Eng kichik elementni toping va uni birinchi o‟ringa qo‟ying.a[1] element 
bilan joyini almashtiring. 
•
Qolganlaridan eng kichigini toping va uni ikkinchi o‟ringa qo‟ying a[2] binan 
o‟rnini almashtirng,va shunday davom etadi. 
Ushbu usil bilan saralashda yozuvlarning tartibga solingan ketma-ketligi xotiraning 
dastlabki ketma-ketlik joylashgan uchastkasining o‟zida tashkil etiladi. Birinchi o‟tish 
davomida eng kichik element izlanadi. Bu element topilganidan so‟ng uni dastlabki ketme-
ketlikdagi birinchi element bilan joyi almashtililadi, natiyjada eng kichik element tulayotgan 
tartiga solingan ketme-ketlikda birinchi element xolatini egalaydi. 
So‟ngra qolgan elementlari ichidan keyingi eng kichik element izlanadi. Topilgan bu 
element xam dastlabki ketma-ketlikning ikkinchi element bilan joyi almashtiriladi. Bu 
jarayon barcha elementlar oshib boruvchi tartibda saralanib bo‟lgunga qadar davom etadi. 
I 
1 
2 
3 
4 
5 
6 
A(i) 
10 
4 
11 
9 
7 
2 
1-o‟tish 
2 
4 
11 
9 
7 
10 
2-o‟tish 
2 
4 
11 
9 
7 
10 
3-o‟tish 
2 
4 
7 
9 
11 
10 
4-o‟tish 
2 
4 
7 
9 
11 
10 
5-o‟tish 
2 
4 
7 
9 
10 
11