Binary Search without Infinite Loop

Revision en1, by AFGhazy, 2015-09-20 01:02:27

Hey, Codeforces I suffered for awhile from writing efficient codes for binary searching, but recently I found an efficient way using bit masking. Say you want to maximize a result using binary search and good function that return true if it's oky or false otherwise. so our binary search would be like that:

__int64 r = 0; for(int i = 62; i >= 0; --i) { if( good(r + (1LL<<i)) ) r += (1LL<<i); }

now you can binary search with out usage of variables such as low and high and middle which would lead to infinite loops.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English AFGhazy 2015-09-20 01:02:27 571 Initial revision (published)