Searching between array indicies

I want to search between two array indicies as fast as possible for the largest element. I have an algorithm but i want to make it faster. I am thinking to use a heap but im not sure how i would implement it. So far this is what i am doing:

I sort the array in ascending order storing each numbers value and original position in the array and then for each pair of indicies i start at the end of the array and if the original value is between the pair of indicies then take it as the largest. when i have something like 10,000,000 pairs it takes about 50 secs instead of 10 mins doing it by searching through each pair linearly(?).

But what i want to do is not have to search from the back of the array linearly, instead i want to search through by log(n) but i am having trouble creating a structure that can do this because it has to be sorted with the largest position at the top but the original position has to also be taken into account. Does anyone know how to improve this search time???