finding max/min in a sorted array

This is a discussion on finding max/min in a sorted array within the C++ Programming forums, part of the General Programming Boards category; Okay, I know this is probably really simple. I know how to find max/min in an unsorted array, but what ...

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    17

    Question finding max/min in a sorted array

    Okay, I know this is probably really simple. I know how to find max/min in an unsorted array, but what about if the array is sorted? Is it the same thing as this, in an unsorted array:

    Code:
    int smallest (int arr [], int num) 
    {
         int smallestsofar = arr [0];
         
         for (int count = 1; count < num; count++) {
              if (smallestsofar > arr [count])
              smallestsofar = arr [count];
         }
         return smallestsofar;
    }
    Or is there a simpler way than going through all that when the array is sorted? Would it be a binary search or what? How would I go about doing it?

  2. #2
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    um, the smallest in a sorted array, for example if it's sorted from low to high, would be the first element of the array, the largest being the last.

    min = arr[0];
    max = arr[size-1];

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If you don't know if the array is sorted or not, you'll need to proceed as if the array was unsorted (more general, works in all cases). If the sortedness of the array is a precondition, then use the first and the last element.

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Are... you... SERIOUS?

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299

    Question WTF!

    Quote Originally Posted by brewbuck View Post
    Are... you... SERIOUS?
    Yeah I can't believe it either.

    I'm sorry I have to refrain from saying anything furthur.

  6. #6
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434
    lol

    Your approach will work with a sorted and unsorted, but as was said, if it's sorted... Then the first element array[0] will be the smallest and the highest element array[size-1] will be the largest

    Think these things through!!!!!!!

    haha

    =D
    "Anyone can aspire to greatness if they try hard enough."
    - Me

  7. #7
    Registered User
    Join Date
    Apr 2007
    Posts
    17

    Angry

    Quote Originally Posted by iMalc View Post
    Yeah I can't believe it either.

    I'm sorry I have to refrain from saying anything furthur.
    Okay, that's uncalled for and not really fair. I was a beginner and basically a n00b. You shouldn't insult me just because I was first starting c++. Everyone has to start somewhere, you know. It was a stupid question, but who the hell cares what you think.

  8. #8
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Crcullen3916, i think the comments were due to the fact that what you already knew (unsorted) was harder to do than what you were asking (sorted). because of this, people will be surprised that you are asking the easier question, even after knowing the solution to the more difficult one.

    sometimes when your starring at code for hours or trying to solve a seemingly complex problem, we will often miss the obvious solution, and are making this more difficult than it has to be. KISS!

    edit: and as others have said, if you have an algorithm to find the min/max in an unsorted array, it will work with no change on a sorted array. notice that the complexity of finding the min/max in an unsorted array is O(n) (at most n comparisons, where n is the size of the array). finding the min/max in a sorted array can be done in constant time O(1) (1 step no matter what size of the array).
    Last edited by nadroj; 09-22-2008 at 10:14 PM.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Nobody's comments had anything to do with you starting C++. You simply had a simple logic problem to solve and youre brain must have been temporarily completely scrambled. Try not to think so hard . My appologies.

    btw, Please don't revive very old threads (I'm going to regret bumping it by adding this in fact).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,602
    btw, Please don't revive very old threads (I'm going to regret bumping it by adding this in fact).
    Speaking as a user, not a moderator, I'd say that in this case it is fine. Crcullen3916 started the thread and the issue was not acknowledged as resolved. Usually the irritating thread necromancy is when a random user searches and finds an old thread, and then tries to get help on that old thread for his or her new problem that is presumably related to the one in the old thread.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding array dimensions
    By deviousdexter in forum C# Programming
    Replies: 3
    Last Post: 11-12-2008, 09:34 AM
  2. Puzzled.
    By silhoutte75 in forum C Programming
    Replies: 13
    Last Post: 01-21-2008, 04:17 PM
  3. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 01:02 PM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Merge sort please
    By vasanth in forum C Programming
    Replies: 2
    Last Post: 11-09-2003, 11:09 AM

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