为什么向大小为N的有序数组插入一个新元素在最坏情况下需要访问2N次数组?

Question

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 Value get(Key key)
    {
        if(isEmpty())
            return null ;
        int i = rank(key) ;

        if(i<N && keys[i].compareTo(key) == 0)
            return values[i] ;
        else
            return null ;
    }

    public void put(Key key , Value value)
    {
        int i = rank(key) ;

        if(i<N && keys[i].compareTo(key) == 0)
        {
            values[i] = value ;
            return ;
        }
        for(int j=N ; j>i ; j--)
        {
            keys[j] = keys[j-1] ;
            values[j] = values[j-1] ;
        }
        keys[i] = key ;
        values[i] = value ;
        N++ ;
    }

    public int rank(Key key)
    {
        int lo = 0 ;
        int 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 ;
    }
}

书上说“向大小为N的有序数组中插入一个新元素在最坏情况下需要访问2N次数组”，这是为什么？
我理解的是N次访问在Key数组，另外N次的访问在Value数组，这么想对吗？

Answer 1

你的binsearch写的不对吧. (0, 2, 4) 插入 1, 结果得到 (1, 0, 2, 4)吧