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.
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.
