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.
Auto comment: topic has been updated by BanazadehAria (previous revision, new revision, compare).
As a general idea, this seems fine. I see two potential issues:
a[mid]but setr=m, is this a typo just in this post or maybe you have it in the real code too?l=-1. This can be what you want, but do you handle this case?To debug, you can add
assert(p(a[l]) == false)andassert(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?
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]
2-Last Index that is == target(upper_bound)
p(x) ==> Everything that is >x is false and everything is <=x is true [l,r)
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:
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.
you're right, those two were the wrong way around. It should be
v <= vec[i]Can we do something like this for this?
Is this correct too?
I'm not sure if I understand your question correctly, but:
0) I'm assuming that
p(x)==trueshould bep(mid)==true1) I think your definition of p(x) is wrong. What if you first ask a value too big? You will have
p(x)=falseso 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.
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.