Binary Search Messed Up Or not?

Revision en1, by BanazadehAria, 2019-06-03 10:15:39

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;

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.

Tags #binary search, invariants

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)