How to solve this using Binary search ?

Правка en1, от daihan, 2019-06-27 18:46:46

I want to solve this problem 1175C -Electrification , using binary search but got stucked . I checked many code of red coders whom used binary search . But it is hard to guess the logic from code . Can anyone explain what is the binary search approach ?

I tried myself using binary search . My approach was: just pick an mid , f2(mid) <= f2(mid+1) that means all values from mid+1 to high are greater , so high=mid . Else low=mid;

Here f2(x) function takes a value and push all abs(ar[i]-x) to vector then sort it and return kth value [hence i used 0 based index] .

This code fails when f2(mid)==f2(mid+1) .

**my code**

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский daihan 2019-06-27 18:46:46 1554 Initial revision (published)