Binar qidiruv Bo’lib tashla va hukmronlik qil

Binar qidiruv

Reja:

1. 
   Chiziqli qidirish
   
2. 
   Ikkilik qidirish algoritmi ishlash prinsipi
   
3. 
   Binar qidiruv
   

Bo’lib tashla va hukmronlik qil

Eng mashhur algoritm — bu ikkilik qidirish (binary search). Ikkilik qidirish algoritmi saralangan arraydan element topishning eng samarali algoritmlaridan biri. Chiziqli qidirish

Chiziqli qidirish algoritmi juda oddiy algoritm bo’lib, u arraydagi har bir elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi. Algoritm murakkabligi O(n) bo’lib, bu real hayotda juda ham sekin bo’lishi mumkin. Tasavvur qilaylik Facebookning 1 mlrd foydalanuvchisi bor va foydalanuvchi o’z profiliga kirmoqchi. Bunda Facebook foydalanuvchi loginini chiziqli qidirishdan foydalanib tekshiradigan bo’lsa va bunda kompyuter sekundiga 10⁶ ta loginni tekshirgan taqdirda ham, o’sha foydalanuvchi profiliga kirishi uchun 1000 soniya (16.6 daqiqa) kutishi kerak bo’lardi. Shu sababli ham bunday holatlar uchun bizga samaraliroq algoritmlar kerak bo’ladi.