Thanks for the suggestion. It really helps a lot…@shoom
Actually, even when I was figuring out what the correct ratio should be, I knew very well that it has to be something of the format (1:k) such that k>1
Now, I started imagining that what if I had to discard the left half of the array at each step and always move rightwards (Basically was trying to figure out the mechanism of my algo if answer was 150,000). So when you needed to move all the way to the right, then it was IMPERATIVE FOR ME THAT EVEN WHEN I AM DOING SO, I SHOULD BE DOING IT IN LESS NUMBER OF STEPS.
This feeling was not to avoid a TLE, I already knew I wont be getting that (Thats because I coded in Python - a slow language when runtimes are considered) but just to lessen the number of steps…
So I decided not to just find out that ‘k’ in the ratio, rather finding out The least possible ‘k’ so that when I am discarding the left part (And moving rightwards, I am discarding a good amount of it) A long contest ; so I was technically free to experiment more rather than Straight up going for an AC.
Even I believe that the ratio is that part of my version of solution with which a lot of people can play and a lot of ratios would lead you to getting an AC verdict
But for me (Its just for me maybe someone else’s opinion differs here) —>
The least number of steps at cost=150 (In worst case) could be achieved very much optimally with a ratio of 1:3.5 in the best possible way, either if the Answer to the question is at the extreme left (that is answer is ‘1’) or at extreme right (Answer is ‘150,000’)
That’s the reason, for me : The Golden Ratio was always 1:3.5
But its true that this is correct for worst case cost of 150, otherwise if ‘c’ is changed, then the ratio would differ.
Once again, I am not very much experienced, so If I am thinking something wrong… Please let me know…!!!