BanazadehAria's blog

Binary Search Messed Up Or not?
By BanazadehAria, history, 6 years ago, In English

Hi I have a predictor function and I want to find the last false element in my array that is not true for that element And I think the correct invariant for this one is my p(a[l]) is always false and p(a[r]) is always true so at the end l is my result index.

And this is my code==>

int l=-1,r=n-1; // First index in my array is 0 and last is n-1

while((r-l)>1){

int mid= l+(r-l)/2;

  if(p(a[mid]){

      r=m; // R now is true and invariation holds


  else l=m; // L is now false and invariation holds

}

cout << l; // Now l is the last false element because r is true and r-l==1

But my code doesn't return the true result in a lot of questions that I have solved in binary search but In the first, I have set an invariant and I think it must be true because I have proved it by invariant.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by BanazadehAria (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

As a general idea, this seems fine. I see two potential issues:

  • You check a[mid] but set r=m, is this a typo just in this post or maybe you have it in the real code too?
  • If all elements are true, you end up with answer l=-1. This can be what you want, but do you handle this case?

To debug, you can add assert(p(a[l]) == false) and assert(p(a[r]) == true) at the beginning of each loop, you will see the exact moment when it fails.

If none of the above solves your issue, maybe you can show an example of a code where it actually fails?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Thank you for your reply it was your number 2 :|

    And Can you tell me Is my invariants for this invariations and codes of binary search correct? (Sorry For my questions, Im actually 4-day newbie)

    1-First index that is == target(lower_bound in c++)

    p(x) ==> Everything that is =x is true (l,r]

    l=-1,r=n-1;

while((r-l)>1){

              int mid = l + (r-l)/2;
     
              if(p(x)==true){
      
                       r=mid;

              else

                       l=mid;


} return r;

    2-Last Index that is == target(upper_bound)

    p(x) ==> Everything that is >x is false and everything is <=x is true [l,r)

    int l=0,r=n;

while((r-l)>1){

      int mid=(l+r)/2;
     
      if(p(x)==true){

            l=mid;

      else r=mid;
 
}return l;
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +13 Vote: I do not like it

      You can use the codeforces "block code" functionality to make your code easier to read. Also, wrapping it in a spoiler makes it waste less space. They are at the two rightmost icons on top of the edit text field. Result looks like this:

      code
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        I don't really understand what do you mean by smallest I such that vec[i]<=v i think its always index zero, and if index zero is not <=v then there is no index in that aray that is <=v.

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

          you're right, those two were the wrong way around. It should be v <= vec[i]

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

            Can we do something like this for this?

            l=-1,r=n-1;// res is in (l,r] range

while((r-l)>1){
      int mid = l+(r-l)/2;
      if(vec[mid]>=target) r=mid;
      else l=mid;
}return r;

            Is this correct too?

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

      I'm not sure if I understand your question correctly, but:

      0) I'm assuming that p(x)==true should be p(mid)==true
      1) I think your definition of p(x) is wrong. What if you first ask a value too big? You will have p(x)=false so the new range will be [mid,r], which is wrong.
      2) Looks correct (assuming I understand the question)

      And I agree with mango_lassi, please use code formatting.

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

        I didn't know about code formatting that yeah by x I meant min it was just a typo. And I didn't understand what you mean by number 1 What is wrong with my prediction function please give me some details.

        → Reply