17-ma’ruza. Qidiruv va saralash

17-ma’ruza. Qidiruv va saralash.

Binar qidirish usuli.

Hammamizga malumki biror bir elementni biror toplamda qidirish juda muhim masaladir. Agar biror to`plamni massiv deb qarasak va massiv elementlari tartiblangan bo`lsa biz bu massivdan x elementni kopi bilan balki undan ham kamroq qadam bilan toppish mumkin. Bu qidirilayotgan elementning qay holatda turganiga bo`g`liq. Bu o`z navbatida dasturni tez ishlashiga va vaqtdan yutish imkonini beradi. Topish uchun binary(ikkilik) qidirish usulini qo`llash kerak. Bu usul yordamida biz massivdan elementni tez toppishimiz mumkin agar massiv elementlari tartiblangan bo`lsa.

binarySearch(ikkilik qidirish) algoritmini ishlash prinspi quyida keltirilgan.

1. 
   Markazidan element olamiz;
   
2. 
   Agar markazdagi element qidirilayotgan elementga teng bo`1sa, algaritm qidirishni to`xtatadi;
   
3. 
   Aks holatda u ikki ko`rinishda bo`lishi mumkin:
   

• 
  qidirilayotgan element markazdagi elementdan kichik bo`ldi. Bu holatda qidirish markazdagi element old tamonidan amalga oshiriladi.
  
• 
  qidirilayotgan element markazdagi elementdan katta bo`ldi. Bu holatda qidirish markazdagi element orqa tamonidan amalga oshiriladi.