Simply stated: “Given a list of n unique values, find the ith smallest.”Common Examples• 1st smallest (Minimum)• nth smallest (Maximum)• n/2th smallest (Median)How can we approach solving such problems?Trivial Way: Sort the list and then return the ith position.This is clearly not a good approach for things such as minimum and maximum.This may or may not be a good approach for other problems such as median finding.• In the worst case, finding the minimum requires n-1 comparisons.• Finding the minimum can easily be done using at worst n-1 comparisons:• Call the first item in the list the smallest.• For each item remaining, compare it to the item currently considered smallest and if it is smaller than that item, set this new item as the smallest.• Do other algorithms exist? Sure, but are they better? What would the runtime be of the following recursive algorithm?• Split the list in half.• Find the minimum of each half.• Take the minimum of the two “local” minima returned.Consider the following scenario:You are given a list of coordinates and are asking to return a bounding box for these points.Your getBoundingBox() method would need to find both the minimum x-coordinate as well as the maximum x-coordinate (and then do the same for the y-coordinates).In general, given a list of items, it is easy to find the minimum and the maximum using 2(n-1) comparisons.Can we do better?What is the runtime of the following algorithm to find the minimum and maximum “at the same time” and will it always give the correct results?• Traverse the list once, two at a time, comparing pairs.• As this is done, create two sub-lists: SubList1 for the greater of the pair-wise comparisons and SubList2 for the lesser.• Call the regular maximum algorithm on SubList1 and the regular minimum algorithm on SubList2.What is the runtime of the following algorithm to find the minimum and maximum “at the same time” and will it always give the correct results?• Compare the first two elements in the list. Set the smaller as min and the larger as max.• For the remaining elements of the list:• Pair up and compare the items in each pair.• Compare the smaller of the pair to the current min, replacing it if we have a new min.• Compare the larger of the pair to the current max, replacing it if we have a new
View Full Document
Unlocking...