In this lecture, we'll see how we can implement an ordered dynamic array to hold int. So the difference between this lecture and the previous lecture is this time we do care about the order of the element and the dynamic array. Our OrderedIntDynamicArray class keeps the values in the IntDynamicArray sorted in order from smallest to largest. So we start with the constructor that just calls the constructor in the parent class. This is, of course, also a child class of IntDynamicArray. And now we get to those three abstract methods that we need to implement. Add is of course different from the add for an unordered dynamic array, but we do still need to check to see if we need to expand the array. That's always our first step to make sure that we have enough room in the underlying array for the item we're about to add. This next piece actually finds where we should add the item. Because we're keeping this sorted, we need to make sure we put this new item in the correct place. So what we do is we start our addLocation at 0. So that means we're assuming we're going to add the new item at the very front of our array, but then we do this while loop to actually find out where we really ought to add it. So while ((addLocation < count) because we want to make sure we haven't gone past the end of the valid element in the array. And while whatever is at addLocation is less than item, so we haven't found the place we should add yet, we increment addLocation. So when this while loop ends, addLocation is exactly the index at which we should add the new item. Now that we know where to add the new item, we call this helper method that we'll look at when we get to the end of this class. But basically this helper method shifts everything up from addLocation to the end of the valid elements in the array so that we can then insert the new item at addLocation. And of course, because we just added something to the array, we increment count. So obviously this is harder work than when we were adding an item to an unordered dynamic array because we have to do all the work to make sure that we find the right place. And then move things around to make room for adding that new item in the right place. Removing is also harder. We still do the first part that we did before. We check to see if the item is in the IntDynamicArray. And if it isn't, we return false because there's nothing to remove. But we can't just copy the thing at the end of the array into the location that we want to remove because that is likely to screw up the ordering in the array. So instead what we need to do is we need to shift everything down. And because we're starting here, we're actually going to shift itemLocation + 1 down on to itemLocation. So writing over what's in itemLocation. But we do that from itemLocation + 1 all the way to the end of the valid elements in the array. And then we decrement count because we just took something out of the array. And we return true because we successfully did that work. The IndexOf method is more complicated than the others because this actually implements something called a binary search. So we'll actually talk about binary search in more detail when we do algorithm analysis in the next lesson, but the big idea here is that we pick the middle of the array. And we check to see if that's the item. And if it is, we're all done. But if it's not, we know which side of the array to keep looking in because the array is ordered. So if item is less than the middle it's got to appear in the left-hand side of the array, if it appears in the array at all. And if item is greater than the middle, then it has to appear on the right-hand side of the array, if it appears at all. And we actually just keep doing that until we either find the item or we run out of array to look at, in which case we're all done. So here is code that calculates the middleLocation and the middleValue, the value at that middleLocation. And we check to see if that's the one we are looking for, and if it is that's awesome, we found it. Otherwise, here is where we split the data set. So if the middleValue > item, that means that the item is on the left-hand side, so we shift the upperBound down. So the lowerBound tells us the lowest index for the array or the subarray that we're looking at to try to find our item. And the upperBound gives us the upper index for that subarray. So if we keep shifting lowerBound and upperBound, then we can sort of keep shrinking the subarray that we're looking at at the correct location based on the item in the ordering in the array until we get down to one element, or we find the item we're looking for. We also are checking here whether lowerBound is greater than upperBound. But I will say that this code that I provided actually had an error in it. And so this is the buggy code, just so you can see the error. And then there's correct code here. And I address this in more detail in the dynamic array's reading. So you should go sort of read through what happened with the bug and why I changed it this way and so on. We will actually see when we get to module three of the course another way to do binary search, and it's called recursion. And we'll just wait until we get there, but it's actually a pretty powerful way to approach this problem and lots of other problems. And that actually might seem more clear to you what's going on. But if you don't really understand what's going on here, make up an array with a pencil and paper and go look for an item in it and walk your way through the code. And you'll see that this actually does a binary search to try to find the item. And we can only do a binary search because the array is ordered. I mentioned the ShiftUp and ShiftDown helper method, and here they are. So ShiftUp, we pass in the index and what we do is we run i from count down to the index just above where we want to start shifting, and we decrement i. So we're starting at the right-hand side. And we keep setting whatever is at i to whatever is the element just before that element. So we're copying everything up here, starting at index. Similarly, ShiftDown does something much like ShiftUp except we start at index. This one actually goes from left to right. We start at index and as long as we're less than count we increment i, and we copy the element at index i into the element at index i- 1. So you should be able to see how this is copying everything down one space. And that's it for our OrderedIntDynamicArray. As you can tell, the code that we write to keep our IntDynamicArray ordered is more complicated than when we didn't care about the ordering of the elements in the array. To recap, in this lecture we saw how we can implement an ordered dynamic array class to hold ints.