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

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

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.

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

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

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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?

  • »
    »
    5 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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;
    
    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

      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
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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.

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

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

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

            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?

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

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.