Errichto's blog

The most comprehensive Binary Search lecture
By Errichto, 6 years ago, In English

I recorded a 30-minute lecture about binary search. It should allow you to really understand it and stop guessing about +1 in random places. Enjoy.

https://www.youtube.com/watch?v=GU7DpgHINWQ

Consider watching with captions on and with x1.25 speed.

  • Vote: I like it
  • +233
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
6 years ago, # |
  Vote: I like it +34 Vote: I do not like it

ETA — Blogewoosh #8?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you, but you didn't mention invariants.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I think I explained how to approach BS problems with the logic behind that. How would invariants help more?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please tell how to approach for problems such as https://mirror.codeforces.com/contest/1169/problem/C

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Code: 54682960

    Observe that the problem is basically asking for the most number of times that a number has to change.

    The problem asks to find the minimum number of operations, which is bounded from 1 to m. Thus, you can binary search for the minimum number of operations in O(log(m)) time.

    That means that you can dedicate O(N) time to checking if it is possible to sort the array using <= a certain amount of operations.

    → Reply
»
6 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Why you don't do analysis of all next educational rounds problems? They are cool to learn topics but sometimes they are hard to understand even with the editorial

→ Reply
»
6 years ago, # |
  Vote: I like it +189 Vote: I do not like it

I am just going to leave this here.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you make a similar video on topics like RMQ and Geometry as many people struggle in those topics?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally 1st.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In case of finding maximum in first increasing and then decreasing array if duplicate elements are present how to handle this?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You can't apply binary search in an array like $$$[1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1]$$$. You can't say which side (left or right) to choose when you ask about the middle element.

    The only exception is that the maximum can be repeated multiple times — if you hit it at least once, you found a correct answer anyway.

    → Reply
»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Really great tutorial , I suggest making such tutorials in number theory topics like segmented sieve or search techniques like ternary search.

I have also implemented the code for the problem to find the maximum value in a mountain range . this is my code , can you kindly review my code if there is any bugs ?

https://ideone.com/5YgGqF

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should compare with adjacent elements, not with maximum so far. Plus your example sequence isn't increasing-decreasing.

    Just solve Leetcode problems from links under the video.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you Errichto for the great lecture.

However I'm concerned about binary search on double:

const double target = 1e18;
double L = 0, R = target;
while (R - L > 1e-9) {
    double mid = L + (R - L) / 2;
    if (mid * mid < target)
        L = mid;
    else
        R = mid;
}

I think previous code won't stop, as when L and R get near the sqrt (which is 1000000000), numbers will be large so precision will be low and comparision (R — L > 1e-9) will never be false.

I prefer use L and Sz (size of the interval), instead of L and R as Sz will always get halved each time, so it's guaranteed to stop.

const double target = 1e18;
double L = 0, Sz = target;
while (Sz > 1e-9) {
    double mid = L + Sz / 2;
    if (mid * mid < target)
        L = mid;
    Sz /= 2;
}

We can also limit the iterations by log of the number.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The thing is it's impossible to get precision $$$10^{-9}$$$ for that big numbers anyway. The precision of your code is for sure bigger than $$$10^{-9}$$$. In a problem from a contest, either values will be smaller or they will ask for relative or absolute error and then we should check that instead of just an absolute error.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi Errichto, When there will be a lecture on dp?

→ Reply
»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone explain me where to use left+1 and Right -1 or not to use -1 or +1 . Watched the video but couldn't find any solution to this problem :) ;

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You might want to read this blog, and you'll realize the meaning of the +1 or -1 according to the context.

    → Reply