algorithm - 二进制搜索符号表实现进入无限循环

我正在尝试实现“有序数组中的二进制搜索”，摘自罗伯特·塞吉维克和凯文·韦恩的《算法》（第四版）一书（第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循环中有一些问题。

最佳答案

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

关于algorithm - 二进制搜索符号表实现进入无限循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48435245/