Блог пользователя Gordon-Freeman

binary search
Автор Gordon-Freeman, история, 3 месяца назад, По-английски

Can someone explain to me how do we choose ranges when doing BinarySearch i solved a lot of BS problems but to be honest i alwayes try differnt ways until one of them work... by mean whats the diffence between writing while(l<r) and while(l<=r) and while(l+1<r)...etc and when do we set r=mid and when r=mid-1 and same for l , please someone explain them all this is the only thing confuse me at BS problems

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

»
3 месяца назад, # |
← Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

This is how I usually approach the binary search implementation.

First, I define an invariant for the pointers. For example, in some cases, I want to ensure that the left pointer (l) always points to a position that is strictly less than the answer, while the right pointer (r) should always be greater than or equal to the answer.

This approach is useful in cases where we want to find the lower_bound() of the answer, meaning the first element that is greater than or equal to x.

Based on that, I use the following implementation:

The initial value of l should satisfy < f(l) == false, meaning l points to a value less than the answer. The initial value of r should satisfy >= f(r) == true, meaning r points to a value greater than or equal to the answer. Next, I use the condition while (l + 1 < r). This ensures that when the loop exits, l and r are adjacent (l = r - 1), and we can determine that r will be the first element that is >= x.

To calculate the midpoint, I use:

int mid = (l + r) / 2;

if(f(mid)){
	r=mid; //this is because we know that mid is >= ans. But we dont know about mid - 1
}else{
	l=mid; // we know mid < ans
}

When the algorithm finishes you will have in r the first element >= x.

The main idea is to set that invariant (l < answer, r >= answer) and then the implementation gets easier.

This is how I approach BS problems. Correct me if there are any errors

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

    I think using the below formula is better in handling large constraints.

    mid=l+(r-l)/2;
    → Ответить
»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I always do:

while (l<=r) {
    mid=(l+r)/2;
    if (check(mid)) {
        res=mid;
        r=mid-1;
    }
    else l=mid+1;
}

Change the r=mid-1 and l=mid+1 depending on whether you need the maximum whatever or minimum whatever.

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

    Can you give a small example to make sure iam getting it righ , thanks

    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      For example, if we have [1,3,5,7,9] and we are searching for the next number greater than 6

      set l=0, and r=4 (highest index),mid,res (predefined outside of while loop)

      First iteration of while loop: mid=(l+r)/2=(4+0)/2=2 check if vec(mid) (5)>6 it isn't, continue otherwise change l from 0 to mid+1 which is 2+1=3

      Second iteration of while loop: set mid=(l+r)/2=(3+4)/2=7/2=rounded down: 3 check if vec(mid) (7) >6, it is as 7>6: change r to mid-1 (r is now 2 and l is 3) update res to be mid (the index of the value)

      No third iteration of while loop, as it violates l<=r (3<=2 not true)

      Hope this helps! Feel free to ask me any questions.

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

easy:

left search:
l, r = 0, n - 1
l <= r
l = m + 1
r = m - 1
return m

.

efficient:

left search:
l, r = 0, n - 1
l < r
l = m + 1
r = m
return l

right search:
l, r = 0, n
l < r
r = m
l = m + 1
return l - 1
→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    why in right searching you returning l-1 why not r

    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Here l == r. When l == r the loop end.

      .

      Let t = target

      In case of left, logic is:

      if a[m] < t:
    l = m + 1
else:
    r = m

      So a[m] == t will occur in else block. Here a[m] == a[r] == t.

      .

      In case of right, logic is:

      if a[m] > t:
    r = m
else:
    l = m + 1

      So a[m] == t will occur in else block. Here a[m] == a[l - 1] == t. That is why we have to initiate r = n in this case.

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

      Note: '<=' check two conditions '==' and '<'. In efficient method, we are avoiding '==' both in while condition and in if-else block.

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

There is a course on Codeforces which has a section on binary search with lots of problems. Go to EDU

→ Ответить
»
3 месяца назад, # |
← Rev. 4   Проголосовать: нравится +15 Проголосовать: не нравится

case 1 : if you want to get the min val

check() min, min+1, min+2, ..., x are true, and x+1, ... max, are false（min <= x <= max） 

int l = min, r = max + 1;//left closed interval, l <= x < r 
while(l + 1 < r){//while x can't be determined
    int mid = (l + r) / 2;//l < mid < r
    if(check(mid)) l = mid;//still, l <= x. 
    else           r = mid;//still, x < r.
}
return l;//(l = x) + 1 == r

case 2: if you want to get the max val

check() min, min+1, min+2, ..., x-1 are false, and x, ... max, are true（min <= x <= max）

then we search x-1.

int l = min - 1, r = max;//left closed interval, l <= x-1 < r  
while(l + 1 < r){//while x-1 can't be determined
    int mid = (l + r) / 2;//l < mid < r
    if(!check(mid)) l = mid;//still, l <= x-1. 
    else           r = mid;//still, x < r-1.
}
return r;//(l = x-1) + 1 == x == r,
→ Ответить