Algoritmdan nazorat savollariga javoblar Algoritm nima

1.

int binsearch(int x, int n) {

int L = 1, R = n+1;

while (R-L > 1) {

int M = (L+R) / 2;

if (a[M] <= x)

L = M;

else

R = M;

}

if (a[L]==x)

return L;

return -1;

}

2.

int binsearch(int x, int n) {

int L = 1, R = n+1;

while (R-L > 1) {

int M = (L+R) / 2;

if (a[M] < x)

L = M;

else

R = M;

}

if (a[R]==x)

return R;

return -1;

}

1. 
   Massivda binar qidiruv algoritmini tushuntirib bering.
   

Binar qidiruv

• 
  Bizga o’sish tartibda saralangan bir o’lchamli massiv berilgan:
  
• 
  4 6 8 10 15 20 21 50 63
  
• 
  Va biror son beriladi. Maqsad bu son berilgan massivda bor yoki yo’qligini aniqlash. Agar bor bo’lsa uning pozitsiyasini chiqarish. Masalan 10 soni massivda bor va pozitsiyasi 4. 16 soni esa massivda yo’q. Massivda yo’q bo’lsa bunga javob tariqasida masalan -1 ni javob sifatida qaytarish mumkin.
  
• 
  Chiziqli qidiruv orqali har bir so’rov uchun O(n) javob bersak, agar savollar soni m ta bo’lsa O(nm) operatsiya talab qilinadi.
  
• 
  Binar qidiruv algoritmi har bir savolga javobni tez topishga imkon beradi.