finding max/min in a sorted array

**Crcullen3916** · 05-01-2007

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?

**indigo0086** · 05-01-2007

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];

**anon** · 05-01-2007

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.

**brewbuck** · 05-01-2007

Are... you... SERIOUS?

**iMalc** · 05-02-2007

Originally Posted by brewbuck

Are... you... SERIOUS?

Yeah I can't believe it either.

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

**Junior89** · 05-02-2007

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

**Crcullen3916** · 09-22-2008

Originally Posted by iMalc

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.

**nadroj** · 09-22-2008

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).

**iMalc** · 09-23-2008

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).

**laserlight** · 09-23-2008

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.

Thread: finding max/min in a sorted array

Thread Tools

Search Thread

Display

finding max/min in a sorted array

WTF!

Similar Threads

Finding array dimensions

Puzzled.

arrays vs lists? And containers in general!

Unknown Memory Leak in Init() Function

Merge sort please