Monotonicity. If you can show that you don't have enough operations to make $$$x$$$, then you definitely don't have enough for $$$x + 1$$$. And if you can make $$$x$$$, then it's only fewer operations to make $$$x - 1$$$. So you have that you can increase the median by all numbers on the range $$$[0, a]$$$ for some $$$a$$$, and you can't increase it by any number on $$$[a + 1, \infty]$$$. Your goal is to find that $$$a$$$, and you can binary search on it.

(Also, you don't actually need binary search for this problem, but it seems to make implementation somewhat easier)

Here some tips about binary search problem:

1. If for every possible value we need to check it is a valid solution or not and this validity comes with increasing or decreasing order then that kind of problem maybe solvable by binary search. That O(n) checking part only need to be done O(log n) times. That makes total complexity O(n log n).

2. Once one of my friend notice a very peculiar pattern about binary search problem. It not always true. But it often helps me to figure out a problem is binary search or not. The pattern is: You are given an array size N, another value M and array of N elements. And asked to find something in array related to the value M. This type of problem is often binary search. So if you see input of a problem something like this —

N M
A[1] A[2] A[3] ..... A[n]

You firstly check if it is solvable by binary search or not. If it is, then maybe you have figured it out faster than many other contestant.