二进制搜索符号 Table 实现进入无限循环

Question

我正在尝试实施 'Algorithms (fourth edition) by Robert Sedgewick & Kevin Wayne' 一书中的 'Binary Search in an ordered array'（第 381 页）。但是我的代码进入无限循环。请帮忙。下面是代码：

public class BinarySearchST<Key extends Comparable<Key>, Value>{
    private Key keys[];
    private Value values[];
    private int N;

    public BinarySearchST(int capacity){
        keys = (Key[]) new Comparable[capacity];
        values = (Value[]) new Object[capacity];
    }

    public int size(){
        return N;
    }

    public boolean isEmpty(){
        return N == 0;
    }

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

    public Value get(Key key){
        if(isEmpty())   return null;
        int rank = rank(key);
        if(rank < N && key.compareTo(keys[rank]) == 0)
            return values[rank];
        else
            return null;
    }

    public void put(Key key, Value value){
        int rank = rank(key);
        if(rank < N && key.compareTo(keys[rank]) == 0){//key already existing, just update value.
            values[rank] = value;
            return;
        }   
        for(int i = N; i > rank; i--){
            keys[i] = keys[i-1]; values[i] = values[i-1];
        }

        keys[rank] = key;
        values[rank] = value;
        N++;
    }

    public static void main(String[] args){
        BinarySearchST<String, Integer> st = new BinarySearchST<String, Integer>(10);

        st.put("A", 10);
        st.put("B", 100);
        st.put("C", 1000);
        StdOut.println(st.get("A"));
    }
}

这对我来说似乎是正确的，但看起来像 put() for 循环中的一些问题。

Answer 1

使用int mid = (lo + hi)/2.

您正在使用 int mid = (lo+(hi-lo))/2，这会减少到 hi/2。所以，最终你的 middle 将小于你的 lo 并且不会收敛导致无限循环。

二进制搜索符号 Table 实现进入无限循环

Binary Search Symbol Table implementation going inside infinite loop

algorithm

symbol-table