Learning_CP's blog

Binary Search Doubt
By Learning_CP, history, 8 years ago, In English

Hello All, I have doubt in Binary Search Algorithm. Like in yesterday's contest 417(Div. 2), there was a problem C Sagheer and Nubian Market . I saw in the editorial and many solutions of the top coders as well. Some people have started binary Search with while(low <= high) this condition, some have started with while(high — low > 1) this condition and some have did it with while(low < high) . I have a doubt, how do we decide that which loop condition we have to apply and how we get the answer ? Can somebody explain this with yesterday's C problem ! Link to the problem:- Link Thanks !

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

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I also had a lot of doubts about binary search. I read various articles on binary search. This might help you here.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Everybody has a slightly different way of doing binary search. This is normal — just make sure you find your own. Feel free to copy somebody's, or a tutorial's — however, make sure you are 100% confident how it works by practising on many binary search questions until you memorise it.

→ Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

You can use one of these a template:

l = left
r = right // both ends are inclusive
ans = undefined
while (l <= r)
  m = (l + r) / 2
  if (check (m))
    ans = m
    l = m + 1
  else 
    r = m - 1
print ans

or 

l = left
r = right + 1 // right end exclusive
while (l < r) // similar to r - l > 1
  m = (l + r) / 2
  if (check (m))
    l = m // l always contains possible answer
  else 
    r = m
print l

or 

l = left - 1 //  left end exclusive
r = right
while (l < r) // similar to r - l > 1
  m = (l + r) / 2
  if (check (m))
    r = m // r always contains possible answer
  else 
    l = m
print r
→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You can do it any way you want. The main thing is to ensure that answer you are looking for is always in the range from start to end.

Say you define mid = (start + end)/2. Then when end-start = 1, mid will be always be evaluated to start, and you will get stuck in an infinite loop if your update operation is start = mid. To over come this you can do the following:

(All the things below are mentioned assuming your range has values as follows True True True...False False False and you need to find the last true value after which the False chain starts)

  1. Define mid = (start + end + 1)/2 : if the check is true then start = mid if not then end = mid -1 (as we know that it failed for mid, therefore the answer has to be at least one lesser than mid)

  2. Break the loop if it start and end get closer than one : This way you never have to deal with the problem of start not getting updated. Once you're out of the loop you only have to check at most 3 values start, start+1, end

My Submission for the 812C http://codeforces.net/contest/812/submission/27493847 Hope it helped :)

→ Reply