Qidiruv va saralash chiziqli va binar qidiruv algoritmlari

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.