@@ -0,0 +1,2564 @@
+package com.matao.fundamentals.exercises;%0A%0Aimport edu.princeton.cs.algs4.StdOut;%0A%0A/**%0A * Created by matao on 2018/8/22.%0A * %3Cp%3E%0A * Equal keys.%0A * Add to BinarySearch a static method rank() that takes a key%0A * and a sorted array of int values (some of which may be equal) as arguments%0A * and returns the number of elements that are smaller than the key%0A * and a similar method count() that returns the number of elements equal to the key.%0A * %3Cp%3E%0A * Note: If i and j are the values returned by rank(key, a) and count(key, a) respectively,%0A * then a%5Bi..i+j-1%5D are the values in the array that are equal to key.%0A */%0Apublic class Ex_1_1_29 %7B%0A%0A    // Note: find the last element smaller than the key%0A    public static int rank(int key, int%5B%5D array) %7B%0A        int low = 0, high = array.length - 1;%0A        while (low %3C= high) %7B%0A            int mid = low + (high - low) / 2;%0A%0A            if (key %3C array%5Bmid%5D) %7B%0A                high = mid - 1;%0A            %7D else if (key %3E array%5Bmid%5D) %7B%0A                low = mid + 1;%0A            %7D else %7B%0A                // If key equals array%5Bmid%5D, check if duplicates are present.%0A                // And find the position of first element.%0A                while (mid %3E= 0 && key == array%5Bmid%5D) %7B%0A                    mid--;%0A                %7D%0A                return mid + 1;%0A%0A            %7D%0A        %7D%0A        if (array%5Blow%5D %3C key) %7B%0A            return low + 1;%0A        %7D else %7B%0A            return low;%0A        %7D%0A    %7D%0A%0A    public static int count(int key, int%5B%5D array) %7B%0A        int firstPosSmallerThan = rank(key, array) - 1;%0A        int count = 0;%0A        for (int i = firstPosSmallerThan + 1; i %3C array.length && array%5Bi%5D == key; i++) %7B%0A            count++;%0A        %7D%0A        return count;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        int%5B%5D whitelist = %7B1, 1, 5, 5, 5, 7, 7, 7, 9%7D;%0A        int key = 7;%0A        StdOut.printf(%22The count smaller than %25d: %25d%5Cn%22, key, rank(key, whitelist));%0A        StdOut.printf(%22The count equals %25d: %25d%5Cn%22, key, count(key, whitelist));%0A        key = 6;%0A        StdOut.printf(%22The count smaller than %25d: %25d%5Cn%22, key, rank(key, whitelist));%0A        StdOut.printf(%22The count equals %25d: %25d%5Cn%22, key, count(key, whitelist));%0A        key = 1;%0A        StdOut.printf(%22The count smaller than %25d: %25d%5Cn%22, key, rank(key, whitelist));%0A        StdOut.printf(%22The count equals %25d: %25d%5Cn%22, key, count(key, whitelist));%0A        key = 8;%0A        StdOut.printf(%22The count smaller than %25d: %25d%5Cn%22, key, rank(key, whitelist));%0A        StdOut.printf(%22The count equals %25d: %25d%5Cn%22, key, count(key, whitelist));%0A    %7D%0A%7D%0A

add solution to exercise 1.1.29