first of all sorry for my bad English .
i`m tring to solve this problem 448D - Про таблицу умножения , the editorial & accepted solutions solve it with Binary search
with left=0 and right boundary = n*m and they try and count number of numbers less than mid then take decision to move
left or right . i`m asking about that Not all the Number between 1 --> n*m are included in the answer space . for
example if n=m=2 --> 3 not a valid answer for any value of k .
i want to understand how binary search solution never touch these invalid values and produce the right answer ?!
thanks in advance .
It is possible that at some point during the binary search that mid is an invalid value, but that's okay. For a given value of mid, you count the number of elements less than or equal to that value, and then adjust hi or lo accordingly. For each possible value of mid, either there are at least k numbers less than or equal to mid (so the answer is <= mid), or there are less than k numbers less than or equal to mid (so the answer is > mid). Therefore, there will be some point x, such that all numbers >= x fall in the first category and all numbers less than x fall in the second category, and such x is the correct answer. So in your example with a 2x2 table, the number 3 has 3 values less than or equal to it in the table, and the number 2 does at well. So it is impossible for 3 to be the value of x mentioned above since 2 will always fall in the same category as 3 for any k.