Lamentis's blog

Doubt on Binary Search
By Lamentis, history, 16 months ago, In English

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?

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
16 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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?

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think:

  • we will mostly use l <= r when in whole range we have only one possible answer

  • when the whole range contains many possible answer

  1. if you want to find maximum value in it we have to use r - l > 1 to avoid code running in infinite loop ,
  2. if you want to find minimum value in it we have to use l < r to avoid code running in infinite loop
→ Reply