The idea of optimization is to divide the original array into several pieces of the same size and make an auxilary array out of the first elements of these pieces.
For example, if original array is 2 4 7 7 9, the auxilary array will be 2 7 9.
when we look for the index of the query element, first we look it up in the auxilary array. The query element won't necessarily be there, but the auxilary array can show us upper bound and lower bound from which we should start binary search in the original array.
arr_to_k is a flag for cases when the query element is not in the auxilary array. Let me show what's it for using the following example. Let the query element be 4.
Step 1. We look at the auxilary_array. 7>4. We have to go left. arr_to_k = 2
Step 2. We look at the auxilary array. 2<4. We have to go right. If arr_to_k wasn't 1, we would return to 7 and then keep cycling between 2 and 7 in the auxilary array. But the value of arr_to_k says that we have to stop and look for k in the original array, somewhere between the original positions of 2 and 7.
Without this optimization the program coudn't pass time limit. Now it passes it. This optimization is helpful when the size of the array being searched through is big.
