Блог пользователя Lamentis

Doubt on Binary Search
Автор Lamentis, история, 16 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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?

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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
→ Ответить