A hard binary search problem

We have four cases as shown in the comments. Each case, we will have different moving direction.

Pay attention, we are comparing

A[mid] to A[mid + k -1]

with A[mid + 1] to A[mid + k], this exaplains why we have arr[mid] and arr[mid + k] instead of arr[mid + k -1]

Or we can change it to a complicated one.

There is no syntax color for the above code. Check this one:

Data Scientist/MLE/SWE @takemobi