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

Binary search Algorithm doubt.

Автор a_journey, история, 6 лет назад, По-английски

when we do while(low < high )

suppose i get answer at mid =( low + high ) / 2 ;

if i again set low to mid , then there is a possibility that it will go in infinite loop .

for example :

low = 4 , high = 5 mid = 4

now suppose if mid is true and we again set low = mid , then low will be again 4 and it will go into infinite loop . what to do in that case , should we set low = mid + 1 .

how to decide when to set low = mid and when low = mid + 1 .

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

normally (at least this is the most common implementation) the high bound is exclusive and therefore you already terminate when low+1 = high

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

    sorry .. but i couldnt understand what u said.. can u please elaborate

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится 
      int l = 0; //inclusive
int r = n; //exclusive
while (l + 1 < r) {
	int mid = (l + r) / 2;
	if (f(mid)) {
		l = mid;
	} else {
		r = mid;
	}
}

      after that $$$l$$$ is the last value for wich $$$f$$$ is true and $$$r$$$ is the first value for which it is false

      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I'll paste a part of my earlier comment(This is just one way of avoiding infinite loops, many other tried and tested versions exist):

In most BS problems we start with an answer(this can be either lo or hi) and progressively try to optimize it (make it larger or smaller in each iteration as per the requirement) Ex : In a sorted array find first number greater than x -> you can plug 'infinity' at the end of your array and assign lo = 0, hi = n (size of array), In this case you have a possible answer (at hi) and in each iteration you try to push the hi to successive smaller values, during all times you maintain 'an answer' at hi.

For cases when you maintain 'an answer' at hi, use hi = mid, if condition is satisfied and lo = mid + 1 otherwise. For this case mid = (lo + hi) / 2

For cases when you maintain 'an answer' at lo, use lo = mid, if condition is satisfied and hi = mid — 1 otherwise. For this case mid = (lo + hi + 1)/2. [since you've already checked answer at lo]

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

    ok , so we will decide where to maintain our answer . !

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

      I am answering considering this as a question :

      Usually questions which ask to minimize a parameter can be solved by starting the answer at hi and for the one's requiring to maximize the answer start with the answer at lo.

      You'll get a hang of where to initialize the answer once you have solved few questions using this paradigm.

      → Ответить