Searching between array indicies

This is a discussion on Searching between array indicies within the C Programming forums, part of the General Programming Boards category; I want to search between two array indicies as fast as possible for the largest element. I have an algorithm ...

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    14

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

  2. #2
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    Asagohan, it seems to me you need binary search. Follow joshdick's link for more info, or google on it.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    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.

  7. #7
    Registered User
    Join Date
    Apr 2004
    Posts
    173
    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)?
    The cost of software maintenance increases with the square of the programmer's creativity.

  8. #8
    Registered User
    Join Date
    Mar 2005
    Posts
    38

    Asagohan, now you help us out here!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. combining array indicies to form a new type
    By cloudy in forum C++ Programming
    Replies: 1
    Last Post: 06-09-2006, 11:30 AM
  2. 2d array question
    By gmanUK in forum C Programming
    Replies: 2
    Last Post: 04-21-2006, 01:20 PM
  3. Merge sort please
    By vasanth in forum C Programming
    Replies: 2
    Last Post: 11-09-2003, 12:09 PM
  4. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 09:31 AM
  5. searching thru a c++ class array
    By stanleyw in forum C++ Programming
    Replies: 1
    Last Post: 05-29-2002, 10:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21