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

Автор aman_naughty, история, 5 лет назад, По-английски

Can someone please help me in binary search. I am confused whether to use

--> l=0 , h = arr.size()-1 and m = (l+h)/2 and while(l<h)

--> l=0 , h = arr.size() and m = (l+h+1)/2 and while(l<h)

--> l=0 , h = arr.size()-1 and m = l+(h-l)/2 and while(l<h)

--> l=0 , h = arr.size()-1 and m = (l+h)/2 and while(l<=h)

It seems that in some cases some of the above give TLE. Can some experienced community member help me which I should use .

I think many of the beginners face this issue while implementing binary search . A little help would be appreciated

So basically there are confusion regarding

while(l<h) or while(l<=h) or while(h-l>1)

m=(l+h+1)/2 or m=l+(h-l)/2 or m=(l+h)/2

h=arr.size() or h=arr.size()-1

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

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

Just think what exactly you want to happen for intervals of size 1, 2 or 3.

You can watch my video here, https://www.youtube.com/watch?v=GU7DpgHINWQ.

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

    In the description section of your video you recommended solving leetcode binary search problems. Actually I was solving this problem from leetcode : problem

    In the discuss forum on leetcode : link the great StefanPochmann explained a rather new solution which I am unable to understand. Can you help me with that. Also nice video:)

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится

      It's something unique for this problem so you won't use it in other problems anyway ;p the important thing is to understand when you should go to the right, when to the left.

      What he does is he imagines that one part of the sequence is changed into -INF or +INF what tells you to go right or left respectively.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Literally the best video on binary search .

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

Here is what I do:

int start = 0;
int end = n - 1;

while (start <= end) {
    int mid = (start + end) / 2;
    if (check(mid)) LOGIC1
    else LOGIC2
}

The key is to think about what your binary searched values will look like (TTTTTFFFFFF? or opposite) and then about which one you want (first occurrence of T? last occurrence of F?) which mostly depends on the problem and how you defined true/false values. Then you can select either start = mid + 1 or end = mid — 1 in the LOGIC places I wrote. I select these by thinking about what happens at the end case (the destination where we have either TF or FT transition).

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

I don't think that makes a difference.

PS: I wonder if the second implementation is correct?

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

What I do is one of 2 of the following, depending on the problem i'm solving:

int lo=begin, hi=end; //the range(inclusive)
while (lo<hi)
{
    int mid=(lo+hi)/2;
    if (f(mid)) lo=mid+1; // can also be !f(mid) if the problem requires that
    else hi=mid;
}
//lo=hi=result

or

int lo=begin, hi=end; //the range(inclusive)
while (lo<hi)
{
    int mid=(lo+hi+1)/2;
    if (f(mid)) lo=mid; // can also be !f(mid) if the problem requires that
    else hi=mid-1;
}
//lo=hi=result

So I start by writing $$$mid=(lo+hi)/2$$$ and when i write the rest of the while loop I add a +1 if I have $$$hi=mid-1$$$.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится
while(low <= high)
{
   mid = (low + high ) / 2. /// if u use long long .
   else mid = (low + (high &mdash; low)/2) /// if int as it would be safe. 
   do something with mid. 
   store the result of mid if needed.
   then either low = mid + 1 , or high = mid -1 .
}