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

vector<int> vct;
for(int i=0; i<n; i++)
    vct.push_back(abs(ar[i]-val));

sort(vct.begin(),vct.end());
return vct[k];

cin>>tc;

while(tc--) {
    scanf("%d %d",&n,&k);

    for(int i=0; i<n; i++)
        scanf("%d",ar+i);

    int low=0, high=ar[n-1];

    while(high-low>1) {
        int mid=(low+high)/2;

        if(f2(mid)<=f2(mid+1))
            high=mid;
        else
            low=mid;
    }



    printf("%d\n",high);

}


return 0;