Gordon-Freeman's blog

binary search
By Gordon-Freeman, history, 2 months ago, In English

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

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

»
2 months ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

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

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

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

    mid=l+(r-l)/2;
    → Reply
»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

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

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

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

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

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

      → Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
← Rev. 4   Vote: I like it +15 Vote: I do not like it

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,
→ Reply