Binary Search Symbol Table implementation going inside infinite loop

Question

I am trying to implement 'Binary Search in an ordered array' from the book 'Algorithms (fourth edition) by Robert Sedgewick & Kevin Wayne' (on page 381). However my code is going inside infinite loop. Please help. Below is the code:

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"));
    }
}

This appears to be correct to me, but looks like some issue inside put() for loop.

Answer 1

use int mid = (lo + hi)/2.

You are using int mid = (lo+(hi-lo))/2 which reduces to hi/2. So, eventually your middle will be less than your lo and will not converge causing infinite loop.