编辑：二进制插入没有像我认为的那样工作

Question

对Java还是新手；我们的教授希望我们在向此 ArrayList 添加元素时使用非递归二进制搜索。我不断收到越界异常，但我就是找不到原因。在调试和逐步进行时，我还注意到异常行为。对于我的生活，我似乎无法从逻辑上解决这个问题。他还希望我们也为此使用比较方法。我的问题是弄清楚 why/how 这使数组越界。任何指点和建议将不胜感激.....我们的教授年纪大了，需要几天才能通过电子邮件回复，我没有那么长的时间来解决这个问题。这是唯一阻碍我完成剩余任务的因素。

    public void enqueue(E item) {
    if(arr.size() == 0) {
        arr.add(item);
    }else {
        int low = 0;
        int high = (arr.size());
        while (low <= high){
            int mid = (low + high)>>1;
            if(arrComp.compare(arr.get(mid), item) < 0){
                low = (mid + 1);
            }
            else if (arrComp.compare(arr.get(mid), item) > 0){
                high = (mid - 1);
            }
            else{
                arr.add(mid,item);
            }
        }
    }
}

***编辑当我这样做时：

int low = 0;
int high = (arr.size() - 1);
while (low <= high){
    int mid = (low + high) / 2;
    if(arrComp.compare(arr.get(mid), item) < 0){
        low = (mid + 1);
    }
    else if (arrComp.compare(arr.get(mid), item) > 0){
        high = (mid - 1);
    }
    else{
        arr.add(mid,item);
    }
}

}

或者这样：

            if(arr.size() == 0){
                     arr.add(item)
}
            int low = 0;
            int high = (arr.size() - 1);
            while (low <= high){
                int mid = (low + high) / 2;
                if(arrComp.compare(arr.get(mid), item) < 0){
                    low = (mid + 1);
                }
                else if (arrComp.compare(arr.get(mid), item) > 0){
                    high = (mid - 1);
                }
                else{
                    arr.add(mid,item);
                }
            }

    }

两者都获取到运行的方法，但实际上都没有填充数组列表。我不明白为什么这不起作用，从逻辑上讲它应该填充数组而不是吗？运行这次没有错误，但实际上什么也没做。数组大小为 0，在运行ning 之后没有元素，但至少现在运行s。

几乎完全解决了我的问题，但现在出现了一个我无法弄清楚的新问题！！！！

        public void enqueue(E item) {
        int low = 0;
        int high = (arr.size());
        int mid =0;
        int cmp;
        if(arr.size()==0) {
            arr.add(item);
        }/**
        else if(arr.size()==1) {
            cmp = arrComp.compare(arr.get(0), item);
            if(cmp < 0){
                arr.add(item);
            }
            else {
                arr.add(0,item);
            }
        } **/
        else {
            while (low < high){
                mid = (low + high) / 2;
                cmp = arrComp.compare(arr.get(mid), item);
                if(cmp < 0){
                    low = (mid + 1);
                }
                else if (cmp > 0){
                    high = (mid - 1);
                }                   
            }
            arr.add(mid, item);
        }

}

我的循环初始化在别处。截至目前，我的输出是 {2, 3, 4, 5, 6, 1} 在我初始化 arraylist 时使用上述入队方法。我这辈子都无法按顺序填写它。授予，我的初始化是这样的，它已经按顺序排列，但根据我们的分配，我们必须在添加到列表时使用二进制搜索方法对其进行初始化。

为什么第一个初始化的项目停留在列表的末尾？（1），当所有其他值都添加到正确的位置时？是否只是因为 ArrayLists 的 .add 方法添加到列表的末尾，即使它是我添加的第一个值（如果列表大小当前为 0，则使用 .add 方法）？我该如何解决这个问题？

我最初的解决方案，注释掉的部分代码，除了输出{3, 4, 5, 6, 1, 2}之外什么也没做，所以我更加困惑，我现在正在寻求建议。

Answer 1

 int high = (arr.size());// the why

也许您应该以这些方式更新您的代码：

high = arr.size() - 1;
mid = low + (high - low) / 2; // 否则当 low 和 high 很大时（如果 size 很大）它可能会溢出整数；
int cmp = arrComp.compare(arr.get(mid), item); // 避免无意义的比较；

编辑：二进制插入没有像我认为的那样工作

EDITED: Binary insertion not working as I think it should

java

arraylist

binary-search

non-recursive