Can someone explain when to use which variation of equality in Binary Search:
1.)while(l<=r) 2.)while(l<r) 3.)while(r-l>1)
Generally, I use the first one as it seems to be the most comfortable for me. However, when going through other participants' codes, I often see the other two variations. Is there any difference?
It depends on how you want to access your final answer. There is no difference in the result. You should think through how the two implementations are different, but achieve the same result. For example, if you use while l <= r, where will the pointer be when you find your answer?
I think:
we will mostly use
l <= r
when in whole range we have only one possible answerwhen the whole range contains many possible answer
r - l > 1
to avoid code running in infinite loop ,l < r
to avoid code running in infinite loop