Now, we are going to work through the problem of finding

the index of the largest element in an array.

As always, we will start by working an instance of the problem ourselves.

Looking at this array,

we see that 99 is the largest element and it is at index two.

This is a problem where we may get stuck trying to figure out

what we did because we just saw the answer.

What if, instead, we had a million element array?

We can't even draw that in this video,

so we can only see the first few elements here.

How would we find the answer here?

Well, we might start by looking at the first element which is 16,

and then looking at the next element which is 12.

16 is bigger than 12,

so let's move on to the next element which is 43,

and compare it to 16.

43 is larger than 16,

so we want to compare it to the later values until we find something even bigger.

We can continue this process comparing

each element to the largest element that we have seen so far,

and when we find something larger,

updating our information about what is largest.

When we reach the end of the array,

we'll have found the largest element no matter how big the array is.

We don't want to write down all those steps for such a huge array,

so let's go back and apply the step by step approach to our smaller problem instance.

We will want to keep track of the largest so far and where we currently are in the array,

and work through comparing element by element and updating our

largest so far as we go through the array.

So now, let's go to step two,

and write down exactly what we just did.

We started by guessing that the index zero might be the largest element.

Then we started our element by element comparison at index one.

We compared 24 to 17 and found that 24 was larger.

So, we updated our guess for the largest element to 24 found at index one.

Then we compared 99 to 24.

99 was bigger than 24,

so we again updated the largest element we had found so far.

Next, we compared three to 99.

Three is smaller than 99,

so there was no need to update the largest element.

There were no more elements in the array,

so we gave two as our final answer.

Next, we need to generalize these steps.

Why is this zero?

We are always going to start at index zero no matter what array we are using.

However, we should think about the possibility that we might have an empty array.

This is our current guess for the largest index.

We will call it "largestIndex."

Next, we might think about why this number is 24,

and why this number is 99,

and this one is three.

The answer to these questions is that these were elements one,

two, and three of the array.

We can generalize this algorithm by replacing

those specific numbers with their locations in the array.

Next, we should think about why we are comparing

the numbers in the array to the numbers 17,

24, and 99, respectively.

These numbers also come from data in the array of elements zero, one, and two.

So, we can make the algorithm a bit more general like this,

but in doing so,

we have introduced another set of specific numbers that we need to think about.

Why are these indices zero, one, and two?

Our first guess might be that we are counting,

but are we really counting?

We have to be a little bit careful here.

To see why, let's go back to our larger, more complicated example.

In this example, we first compared element one to element zero.

Then we compared element two to element zero.

Here, we found that element two was larger so we updated largestIndex,

and then we compared element three to element two.

The index of the second item in our comparison is not counting since we used zero,

then zero again, then two.

Next, we compare element four to element two,

and then five to two,

at which point, we once again update our largestIndex.

We now compare elements six, seven,

and eight to element five,

and then once again,

find a new larger item at element eight.

At this point, I've figured out what the pattern is.

Think about it for a moment and see if you know what we are doing.

The pattern is that we are always comparing

the current element with the array largestIndex,

so we can update our algorithm to reflect this understanding.

These steps are looking pretty repetitive.

The only thing that does not repeat exactly is that sometimes,

we update the largestIndex,

and sometimes, we do not.

We need to figure out under what conditions we update largestIndex.

We are doing this when the current element is

larger than the largest element we have seen so far.

With that in mind, we can make these steps completely repetitive,

so that we can then express this repetition in terms of counting.

We won't always give an answer of two,

so we should think for a moment as to where this value came from,

and realize that it was the value of largestIndex in our example.

Now, our algorithm says to give largestIndex as the answer in the general case.

This algorithm is pretty general,

but we might think about one corner case.

What if there are no elements in the array?

We would need to handle that case and give back

an answer that indicates "no valid answer."

We will choose minus one as our answer since it is not a valid index in an array.

Next, we would want to test this algorithm.

We'll leave that up to you.

Try it out on a few inputs and convince yourself

that it is correct before we proceed to step five.

Here, we've declared our function,

"findLargestIndex," and written our algorithm as comments inside the code.

The first line describes two steps,

but they should be quite familiar now,

an if statement with a return statement inside of it.

Next, we declare and initialize largestIndex.

Then we have a "for-loop" to count with,

and an "if" statement" to compare array elements to each other.

If the condition is true,

we update largestIndex to be "i."

And at the very end,

we return largestIndex, and we're done.

Index of Largest Element

Pointers, Arrays, and Recursion

Meet the Instructors