Блог

Я должен вернуть количество ключей в таблице в диапазоне [key1, key2], поэтому для примера в строке ключей типа «BEIOU» диапазон от «B» и «U», он должен возвращать 5, поскольку между «B» и «B» есть 5 ключей.»U». Однако моя текущая программа возвращает 4. Если я проверяю ту же строку «BEIOU», но диапазон от «A» до «Z», то он возвращает 5, поскольку между ними 5 ключей, но для «B» и «U» он возвращает 4. Как я могу это исправить?

 public class SortedArrayST<Key extends Comparable<Key>, Value> {
    private static final int MIN_SIZE = 2;
    private Key[] keys;     
    private Value[] vals;  
    private int N = 0;  

    public SortedArrayST() {
        this(MIN_SIZE);
    }

    @SuppressWarnings("unchecked")
    public SortedArrayST(int size) {
        keys = (Key[])(new Comparable[size]);
        vals = (Value[])(new Object[size]);
    }

    public SortedArrayST(Key[] keys, Value[] vals) {
        this(keys.length < MIN_SIZE ? MIN_SIZE : keys.length);
        N = (keys.length == vals.length ? keys.length : 0);
        int i;
        for (i = 1; i < N amp;amp; keys[i].compareTo(keys[i - 1]) > 0; i  );
        if (i < N) { // input is not sorted
            System.err.println("SortedArrayST(Key[], Value[]) constructor error:");
            System.err.println("Given keys array of size "   N   " was not sorted!");
            System.err.println("Initializing an empty symbol table!");
            N = 0;
        } else {
            for (i = 0; i < N; i  ) {
                this.keys[i] = keys[i];
                this.vals[i] = vals[i];
            }
        }
    }

    public int countRange(Key key1, Key key2) {
        int firstkey = 0;
        int secondkey = 0;
        int count = 0;
        if(key1.compareTo(key2)>0) {
            firstkey = rank(key1);
            secondkey = rank(key2);
            count = (firstkey - secondkey   1);
        }
        else if(key2.compareTo(key1)>0) {
            secondkey = rank(key2);
            firstkey = rank(key1);
            count = (secondkey - firstkey   1);
        }
        return count;
    
    }

    public int rank(Key key) {
         int lo = 0, hi = N-1; 
            while (lo <= hi) { 
                int mid = lo   (hi - lo) / 2; 
                int cmp = key.compareTo(keys[mid]);
                if      (cmp < 0) hi = mid - 1; 
                else if (cmp > 0) lo = mid   1; 
                else return mid; 
            } 
            return lo;
        } 


    public static void main(String[] args) {    
        allCountRangeTests();
}
    public static void allCountRangeTests() {
        testCountRange("BEIOU","13456", "B","U", 5);   
        testCountRange("BEIOU","13456", "U","B", 5);  
        testCountRange("BEIOU","13456", "A","Z",5);  
        testCountRange("BEIOU","13456", "C","P",3);   
    }
    
    public static SortedArrayST<String,String> from (String keyData, String valData) {
        int n = keyData.length();
        if ( n != valData.length()) throw new NullPointerException(" from: mismatch sizes");
        String[] keys = new String[n];
        String[] vals = new String[n];
        for (int i=0; i < n; i   ) {
            keys[i] = keyData.substring(i, i 1); 
            vals[i] = valData.substring(i, i 1);  
        }
        return new SortedArrayST(keys,vals);
    }

    public static void testCountRange( String keyData, String valData, String key1,String key2, int expected) {
        SortedArrayST<String, String> x = from(keyData,valData);
        int actual = x.countRange(key1,key2);
        if ( actual == expected)  // test passes
            StdOut.format("countRangeTest: Correct  Keys: %s, key1: %s  key2: %s     actual: %d expected: %dn", keyData, key1,key2, actual,expected);
        else
            StdOut.format("countRangeTest: *Error*  Keys: %s, key1: %s  key2: %s     actual: %d expected: %dn", keyData, key1,key2, actual,expected);
    }
}
  

Я вижу две проблемы, которые вместе могут объяснить ваши результаты. Во-первых, ваши две строки:

 count = secondkey - firstkey;
  

должно быть:

 count = secondkey - firstkey   1;
  

поскольку в любом диапазоне X ..X есть один ключ, а не 0. Это объясняет, почему вы получаете ‘4’, когда ожидаете получить ‘5’. Но это также означает, что вы получите «6», когда сейчас получаете «5». Итак, что-то еще не так….

Если в вашем rank методе, если вы когда-нибудь выйдете из while цикла, вы вернетесь lo , то есть сейчас > hi , поэтому вы вернете число, которое слишком велико. В этом случае вы хотите вернуться hi . Ваш двоичный поиск в остальном кажется нормальным с первого взгляда. Не имея всего вашего кода, я фактически ничего не могу запустить.