Binary search bu
tartiblangan massivda biron bir qiymatni topishlikda juda effektiv bo'lgan search algoritmlaridan biri. Bajarish tezligi - O(logn).Taqqoslash uchun biz bilgan linear search (shunchaki massiv boshidan oxirigacha siklda yurib chiqish) tezligi
O(n). 1000 ta element va eng yomon holatda 1000 ta amal.Aytaylik bizda 4 milliard tartiblangan sonlardan iborat massiv bor. Va ular ichidan berilgan sonning indeksini topishimiz kerak. Va aytaylik shu son massiv oxirida joylashgan ekan (Bu eng yomon holat).
Oddiy linear searchda sikl 4 milliard marta bajarilar edi. Binary Search bilan esa maksimum 32 ta qadamda biz kerakli natijani topa olamiz. 4 milliard vs 32.
Nega 32? Sababi log(4 000 000 000) <= 32.
Logarifm esidan chiqib qolganlar uchun, logarifm sonning teskari darajasi. Masalan: 2^3 = 8 ekvivalent log2(8) = 3
Note: Binary Search bilan ishlay olishlik uchun berilgan massiv albatta tartiblangan bo'lishi kerak.
#binary_search #algorithm
@elyor_dev