### aman_naughty's blog

By aman_naughty, history, 11 months ago, ,

--> 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

 » 11 months ago, # |   +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.
•  » » 11 months ago, # ^ |   0 In the description section of your video you recommended solving leetcode binary search problems. Actually I was solving this problem from leetcode : problemIn 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:)
•  » » » 11 months ago, # ^ |   -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.
•  » » » » 11 months ago, # ^ |   0 Yes. Thanks StefanPochmann just never fails to amaze me. His solutions are so concise and are like if himself set the question XD.
•  » » 11 months ago, # ^ |   +10 Literally the best video on binary search .
 » 11 months ago, # |   -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).
•  » » 11 months ago, # ^ |   0 Thanks. The prefix suffix part is really helpful
 » 11 months ago, # |   0 I don't think that makes a difference.PS: I wonder if the second implementation is correct?
 » 11 months ago, # |   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
•  » » 25 hours ago, # ^ |   0 Hi, Can you please explain why mid = (lo+hi+1)/2 and not mid=(lo+hi)/2 in the second implementation ??Thanks
 » 11 months ago, # | ← Rev. 3 →   +10 while(low <= high) { mid = (low + high ) / 2. /// if u use long long . else mid = (low + (high — 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 . }