CodeTips

Given an array with n numbers, with n - 1 comparisons, we are able to find the smallest number in the array. After we find out the minimum number of the array, we only need n - 2 comparisons to find out the second smallest element in the array. Because there are n - 1 remaining elements. Can we do better than this? The answer is YES. The algorithm works as follows. See the image below. 1) Split the array into groups of two. 2) Get the smaller one out of the two. 3) Keep comparing until we find out the minimum. There are n - 1 comparisons to find out the minimum of the array. 4) Note that the second smallest element is among the elements that were compared with the minimum in the comparison tree. There are lgn elements that are compare with the smallest element. See the double circled elements in the image. Now lgn -1 comparisons are needed to find the smallest value out of the lgn values. The total comparisons  are n - 1 + lgn - 1 = n + lgn - 2.

Given an array of integers, find the maximum and minimum of the array. It seems trivial to find the maximum or the minimum. Let n be the length of the array. O(2n)  Using n - 1 comparisons, we are able to find the maximum. With another n - 1 comparisons, we are able to find the minimum. In order to find the minimum and maximum, the total runtime will be O(2n). Could we do better? How about sort the array first? Using the fastest sorting algorithm,  the time complexity will be O(nlogn), which is more expensive than O(2n). Actually, there is an algorithm with O(1.5n) time complexity. This is how it works. We uses two variables curMax, curMin to keep track of the current maximum when we iterate through the array. The most important point is that each iteration, we will inspect two numbers in the array. Let's name them A and B. We compare A and B first. Then, we compare the larger one with the curMax, and update the curMax if necessary. Also, we compare the smaller on...