Searching between array indicies

[Asagohan]

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???

[joshdick]

Yes.

http://en.wikipedia.org/wiki/Search_algorithms

[quzah]

Are you searching or sorting? If you're just searching an unsorted list, you can't beat just walking the whole thing, because you have to check every single node anyway. If it's sorting, that's an entirely different issue.

But again, if all you're doing is searching through the list to find the biggest, and it's unsorted, you have to visit every single element anyway.

Quzah.

[Togra]

Asagohan, it seems to me you need binary search. Follow joshdick's link for more info, or google on it.

[quzah]

Why on earth do you need a binary search if it's unsorted? How can this possibly help? If it is sorted, all you have to do is look at the last element in the array, that's the highest.

I suspect this should have actually been on sorting, not just searching. As stated, you cannot search an unsorted list faster than simply walking through the whole thing.

Quzah.

[Togra]

Asagohan might want to find the largest element between two variable bounds (that's how I interpret his question). So linear search would mean doing the same thing over and over again, if the search intervals overlap. I believe a better way would be to sort once, then do a binary search per search interval.

[0rion]

Well it won't be faster if he just needs the maximum value of the between 2 indices, which in this case will be O(n) as Quzah said. Sorting an unsorted array just to use binary search in between 2 indexes will be slower that just walking through the elements once, btw why would you want to use binary search on a sorted array when you know the largest element to be at the end of the interval (I could be misreading something here tho)?

[Togra]

Asagohan, now you help us out here!