java - 使用二进制搜索插入有序数组

Question

以下是我到目前为止的内容。问题是我如何找到插入点。我在纸上做了一些手绘，我观察到最终下限和上限相等，插入点总是比下限和上限相等时的索引更高。

我知道网上有很多解决方案，但我真的想靠自己去理解，因为我只在自己学习的时候学习和记住一些东西，而不是试图弄清楚其他人是如何想出解决方案的。

如果有人能指导我就太好了。此外，一旦我得到插入点，我就可以做剩下的事情，即将所有值移动一个索引，以便为插入值腾出位置。

   public void insert(long value) {

            int lowerBound = 0;
            int upperBound = nElems - 1;
            int curIn;

            while (true) {
                curIn = (lowerBound + upperBound) / 2;

                if (a[curIn] < value)
                    lowerBound = curIn + 1;
                else
                    upperBound = curIn - 1;

            }

Answer 1

二分搜索必须检查循环内的三种情况:

1. 搜索到的值小于当前中心元素
2. 搜索到的值大于当前中心元素
3. 该值等于当前中心元素(此时搜索结束)

当 lowerBound 等于 upperBound 并且所讨论的位置不时，二分查找应该中止到搜索的值。

反正查找结束的位置就是你要插入值的位置:如果那个位置的值等于你要插入的值，那么你是在这个位置插入还是之后插入都无所谓.如果比较小，就想在这个位置之后插入，如果比较大，就想在这个位置插入。

我不会给出代码，因为 OP 显然只是要求提示。