aman_naughty's blog

By aman_naughty, history, 3 months ago, , 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 Comments (10)
 » 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.
•  » » 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:)
•  » » » 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.
•  » » » » Yes. Thanks StefanPochmann just never fails to amaze me. His solutions are so concise and are like if himself set the question XD.
•  » » Literally the best video on binary search .
 » 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).
•  » » Thanks. The prefix suffix part is really helpful
 » I don't think that makes a difference.PS: I wonder if the second implementation is correct?
 » 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
 » 3 months ago, # | ← Rev. 3 →   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 . }
{"ft_lang_label":"__label__en","ft_lang_prob":0.9175593,"math_prob":0.8815808,"size":2505,"snap":"2019-43-2019-47","text_gpt3_token_len":645,"char_repetition_ratio":0.10595762,"word_repetition_ratio":0.058035713,"special_character_ratio":0.26826346,"punctuation_ratio":0.09242144,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9863172,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,1,null,null,null,1,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-21T16:58:54Z\",\"WARC-Record-ID\":\"<urn:uuid:896600ec-a251-4a07-bad3-26214229ddf0>\",\"Content-Length\":\"117827\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:7624d694-5d21-4f04-b83f-4c13649aeaa5>\",\"WARC-Concurrent-To\":\"<urn:uuid:d99ef481-696d-4bab-9642-f44523107fb4>\",\"WARC-IP-Address\":\"81.27.240.126\",\"WARC-Target-URI\":\"http://codeforces.com/blog/entry/68569\",\"WARC-Payload-Digest\":\"sha1:7LIDNFQVMERMOALJEGALOOZMKEXKKBHO\",\"WARC-Block-Digest\":\"sha1:4M3UEYIJKTXM2QYGMXI6WWJEIN37NRSY\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570987779528.82_warc_CC-MAIN-20191021143945-20191021171445-00034.warc.gz\"}"}