Binary Search Messed Up Or not?
Difference between en1 and en2, changed 78 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English BanazadehAria 2019-06-03 10:16:27 78
en1 English BanazadehAria 2019-06-03 10:15:39 790 Initial revision (published)