ორობითი ძებნა და ძებნა პასუხზე

ორობითი ძებნა მილიარდში ელემენტს დაახლოებით 30 ბიჯში პოულობს. მისი უფრო დიდი იდეა, ძებნა თავად პასუხზე, ხსნის ოპტიმიზაციის ამოცანებს, რომლებიც ძებნას სულაც არ ჰგავს.

საშუალო⏱ 14 წთ

←ეყრდნობა

2კომპარატორები და სტაბილურობაორობით ძებნას დალაგებული მონაცემები სჭირდება, lower_bound კი იმავე კომპარატორს იღებს, რასაც std::sort.0სირთულე და ზრდის ტემპიშუალედის განახევრება ყოველ ბიჯზე სწორედ ისაა, საიდანაც O(log n) მოდის.

გზას უხსნის→

5ძებნის ორობითი ხეძებნის ორობით ხეში ძებნა არის ორობითი ძებნა, ხის ფორმაში გაყინული.5ფენვიკის ხე (ბინარული ინდექს-ხე)ორობითი ძებნის მსგავსად, ყოველი ბიჯი 2-ის ხარისხებით მუშაობს, ამიტომ განახლებასაც და შეკითხვასაც O(log n) სჭირდება.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01გაანახევრე ძებნის არე

დალაგებულ მასივში შეხედე შუა ელემენტს. თუ ის საძებნია, მზადაა. თუ საძებნზე მცირეა, საძებნი მხოლოდ მარჯვნივ შეიძლება იყოს; თუ დიდია, მხოლოდ მარცხნივ. ორივე შემთხვევაში ერთი შედარება დარჩენილის ნახევარს აგდებს.

შეინარჩუნე შუალედი [lo, hi] ინვარიანტით „თუ საძებნი არსებობს, ის [lo, hi]-შია“. ყოველი ბიჯი: mid = lo + (hi − lo) / 2, შედარება და lo-ს გადატანა mid + 1-ზე ან hi-ს mid − 1-ზე. როცა lo > hi, შუალედი ცარიელია და საძებნი იქ არ არის.

16 → 8 → 4 → 2 → 1: n ელემენტს დაახლოებით log₂ n ბიჯი სჭირდება. 10⁹ ელემენტისთვის ეს 30-ია.

02იფიქრე პრედიკატებით: lower_bound

ორობითი ძებნის ყველაზე სასარგებლო ფორმა „იპოვე x“ კი არა, „იპოვე პირველი პოზიცია, სადაც პირობა true ხდება“.

დალაგებულ მასივზე პირობა a[i] ≥ x არის false, false, …, false, true, true, …, true. ორობითი ძებნა საზღვარს პოულობს: ეს lower_bound(x)-ია. ანალოგიურად upper_bound(x) პირველი a[i] > x-ია, ამიტომ x-ის ასლების რაოდენობა upper_bound − lower_bound-ია.

ასე დაწერა შეცდომების უმეტესობას გაარიდებს:

lo = 0, hi = n; სანამ lo < hi: mid = (lo + hi) / 2; თუ cond(mid), hi = mid, თორემ lo = mid + 1. ბოლოს lo არის პირველი true (ან n, თუ არცერთი).

კლასიკური ხაფანგები: უსასრულო ციკლი, როცა lo არ იძვრის, hi-ზე ერთით აცდენა და (lo + hi)-ის int-ის გადავსება უზარმაზარ შუალედებზე.

03ორობითი ძებნა პასუხზე

ზოგჯერ მასივი საერთოდ არ არის. სამაგიეროდ გთხოვენ უმცირეს მნიშვნელობას, რომელიც მუშაობს: უმცირეს დროს, მინიმალურ ტევადობას, ყველაზე ნელ სიჩქარეს, რომელიც მაინც ასწრებს.

თუ შეგიძლია დაწერო can(t), „საკმარისია t?“, და ის მონოტონურია (თუ t მუშაობს, ყოველი დიდი t-ც მუშაობს), პასუხები ქმნის F F F … T T T. t-ზე ორობითი ძებნა პირველ T-ს პოულობს.

მაგალითი: მანქანებს თითო ნაწარმზე 3, 2 და 5 წამი სჭირდებათ. t დროში ისინი ამზადებენ ⌊t/3⌋ + ⌊t/2⌋ + ⌊t/5⌋ ნაწარმს. საკმარისია t 7-ისთვის? t = 7 იძლევა 6-ს (არა), t = 8 იძლევა 7-ს (კი): პასუხია 8.

აქ ყოველი შემოწმება O(მანქანების რაოდენობა)-ია, ძებნას კი log₂(დიაპაზონი) შემოწმება სჭირდება, დაახლოებით 60, თუნდაც 10¹⁸-მდე პასუხებისთვის.

04როგორ ვიცნოთ ნიმუში

ორობით ძებნას მიმართე, როცა:

მონაცემი დალაგებულია (ან ერთხელ შეგიძლია დაალაგო და მერე ბევრ კითხვას უპასუხო)
პირობაში წერია „მინიმალური მაქსიმუმი“, „მაქსიმალური მინიმუმი“, „უმცირესი დრო, რომლისთვისაც“, „უმცირესი k, რომლისთვისაც“
კანდიდატი პასუხის შემოწმება მარტივია, საუკეთესო პასუხის პირდაპირ აგება კი რთული

პასუხზე ძებნის საკონტროლო სია: განსაზღვრე can(x), დაამტკიცე მონოტონურობა, აირჩიე lo (ნამდვილად ცუდი ან უმცირესი შესაძლო) და hi (ნამდვილად კარგი), მერე ეძებე. დიაპაზონისთვის 64-ბიტიანი მთელები გამოიყენე.

როცა დალაგებული მონაცემი იცვლება (ჩასმა, წაშლა), შეინახე ის დალაგებულ set-ში ან map-ში, რომელიც იმავე lower_bound-ს O(log n)-ში გთავაზობს. ხოლო თუ მხოლოდ კუთვნილება გჭირდება რიგის გარეშე, ჰეშ-სიმრავლე O(1)-ია.

ფასი ერთი შეხედვით

ძებნა დალაგებულ მასივშიO(log n)

lower_bound / upper_boundO(log n)

ძებნა პასუხზეO(log(range) · check)

ერთი სორტირება, მერე q კითხვაO((n + q) log n)

დაიმახსოვრე

ყოველი შედარება [lo, hi]-ის ნახევარს აგდებს, ამიტომ n-ელემენტიან დალაგებულ მასივს დაახლოებით log₂ n ბიჯი სჭირდება.
ჩამოაყალიბე როგორც „პირველი ინდექსი, სადაც მონოტონური პირობა true ხდება“ და lower_bound ყოველთვის სწორად გამოგივა.
თუ can(x) მონოტონურია, x-ზე ორობითი ძებნა ოპტიმალურ პასუხს მისი აგების გარეშე პოულობს.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე, როგორ ნახევრდება ცოცხალი შუალედი [lo, hi] ყოველ შემოწმებაზე. სცადე არარსებული საძებნი და ნახე, როგორ გადაკვეთს lo hi-ს.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

დალაგებული მასივი: ვეძებთ 31-ს

ვეძებთ 31-ს დალაგებულ მასივში (10 ელემენტი). ინვარიანტი: თუ 31 არსებობს, ის [lo, hi] შუალედშია.

ფსევდოკოდი

 1 lo = 0; hi = n-1 2 while lo <= hi: 3   mid = (lo + hi) / 2 4   if a[mid] == x: return mid 5   if a[mid] <  x: lo = mid + 1 6   else:           hi = mid - 1 7 return -1  // not present

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

a = [2, 4, 4, 4, 7, 9]. რას აბრუნებს lower_bound(4) (ინდექსები 0-დან)?

№2

დაახლოებით რამდენი შემოწმება სჭირდება ორობით ძებნას 1 000 000-ელემენტიან დალაგებულ მასივზე უარეს შემთხვევაში?

№3

იპოვე უმცირესი დღიური ტევადობა, რომ ამანათები D დღეში გაიგზავნოს. რატომ მუშაობს ტევადობაზე ორობითი ძებნა?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeBinary Search დამწყები↗LeetCodeFind First and Last Position of Element in Sorted Array საშუალო↗LeetCodeKoko Eating Bananas საშუალო↗CSESFactory Machines საშუალო↗CSESArray Division მოწინავე↗