A&DS S01E05. Binary Search

Algorithms and data structures. Semester 1. Lecture 5.
In the fifth lecture, we talked about various applications of the binary search algorithm, as well as the ternary search algorithm.
Home task and discussion: codeforces.com/blog/entry/83518
ITMO University, 2020

[@chuka231d8]

Content of this lecture:
1. Into of Binary Search & naive implemention
2. Lower_bound & Upper_bound implementation
3. 2 sample problems covering int and double implementations
4. Ternary Search

[@saikoushik1018]

Thank You sir, Its very helpful for me.. Please continue to teach these data structures and algorithms
sir.

[@maninandadeepmedicharla6213]

@Pavel Mavrin fantastic videos really helped a lot. keep posting these kinds of videos

[@shubhamagarwal2998]

Thanks
Thanks
Thanks
Thanks
Thanks
Thanks
-
-
-
-
-
Thanks
Thanks
Thanks

[@jonathanandres1657]

Thanks!

[@franky0226]

Thanks!♥️

[@yashmalik815]

@Pavel Mavrin are these lectures any different from those in the EDU section of codeforces??

[@blitztage3245]

Yes, those lectures are from the perspective of competitive programming whereas these lectures are similar to the ones taught in a Data Structures and Algorithms course in universities

[@vijaykushwah1414]

​@@blitztage3245can u plz send link of that videos/playlist

[@devjoytibarman7623]

thanks

[@abhiraj9990]

@Pavel Mavrin why in 2nd Method r>l+1 ?

[@pavelmavrin]

We need to stop the loop when l and r point to adjacent elements, that is r = l + 1

[@madhukiranattivilli2321]

Hi Pavel,
Your "get the peak point in a curve" problem, which u solved using ternary search (TS)...
Can be effectively solved using BS also, I'm feeling :
loop
break, if r f(m+1) -- as we're on the "falling" section of the curve
l=m, if f(m) < f(m+1) -- as we're on the "raising" section of the curve
endloop
outside the loop -- r == l+1
return l, if f(l) > f(r)
return r
2 questions :
(1) Is this good enough? Or, like yesterday did I once again make a silly mistake?
(2) Could you please suggest PROBLEMS where TS is more effective than BS?
Thanks,
Madhukiran

[@pavelmavrin]

That‘s fine if the function has integer argument. If the argument is a real number, you need something like f(m) < f(m + eps), and then you will have accuracy problems

[@madhukiranattivilli2321]

@@pavelmavrin When does algo end with real numbers? f(m)f(m+eps) sets r=m. We've to stop at some point. Should we've to pre-decide the PRECISION LIMIT, and stop the algo when the precision-limit becomes > eps?
When real numbers are used with TS, is this how we stop the algo?
set m_limit = precision
loop
-- compute m1, m2 from l, r
-- break, if abs(f(m1) - f(m2)) < m_limit
-- rest-of-TS-algo
endloop
Can precision be nano (10⁻⁹) or pico (10⁻¹²)???

[@nikunjjayas4520]

Predicate search....

[@prajwalchoudhary4824]

30:06

[@miku6701]

45:35 Minecraft villager noises

[@xZero_.]

Lol