Блог пользователя DumbCarlsen69

Автор DumbCarlsen69, история, 3 года назад, По-английски

Hello Everyone, Can anyone clarify when we are using binary search. Sometimes in the while loop We write while(l<r) and sometimes we write while (l<=r) depending from question to question ofc.

But I always get pretty confused between the two and ended up either wasting too much time or making many wrong submissions. is there a clear cut distinction like when we should use the first one and when we should use the second one?

Questions like these confuses me a lot https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Thanks!

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Depends on the implementation ofc! But say I have

\\beginning
while(l < r){
   \\attempt to find stuff
}
\\ending

This basically means that once the loop is done, $$$l \ge r$$$. So if $$$l = r$$$, we just got to check if $$$l = r$$$ satisfies the constraints. If $$$l \ne r$$$, then $$$l > r$$$, which is invalid anyhow.

Alternatively, with the following:

\\beginning
while(l <= r){
   \\attempt to find stuff
}
\\ending

we have to check inside the loop if $$$l = r$$$, and in such a case, we have to check if $$$l = r$$$ is valid. But we do also have to be careful here because we don't want infinite recursion when $$$l = r$$$.

So it's primarily an implementation difference. There's no clear cut distinction of when to use one over the other. Both work and are slightly different 'styles'. One does the FINAL checking INSIDE the loop (and needs careful checking to ensure no infinite recursion), the other does the final checking OUTSIDE the loop.

Hope this helps!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

You can simply store what you are finding in a variable named ans and simply use while(l<=r) always. For example you are finding min element for which certain condition is true if it is true at mid then store it in ans and set en=mid-1. When you will be done completing your binary search you will always have the req. answer in the ans variable. Let's take the given question as an example, If you do not want to use lower_bound and upper_bound functions then let's binary search the value. so for finding min place

Code
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I was confused too, did some asking and wrote this.