Binary Search Messed Up Or not?

Правка en2, от BanazadehAria, 2019-06-03 10:16:27

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.

Теги #binary search, invariants

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский BanazadehAria 2019-06-03 10:16:27 78
en1 Английский BanazadehAria 2019-06-03 10:15:39 790 Initial revision (published)