java - 使用二进制搜索在正确的索引处打开数组中的空间

Question

我应该创建两种方法:第一种方法 bSearch 是一种二进制搜索算法。第二种方法 insertInOrder 应该采用我们从 bSearch 方法获得的索引并在数组中找到该索引，通过移动该数组的所有其他元素在该索引处打开一个位置，并将键/整数插入到那个指数。

将从包含 25 个整数的文本文件中接收整数。我不会为此制作任何副本或额外的数组，我应该在 insertInOrder 方法中对索引进行编码然后解码。在这些方法中，key 将是从 int 文件中读取的当前 int，count 将计算已接收到的 int 的数量。我基本上是在构建自己的排序方法，我不能调用任何外部方法，并且数组随时都不会乱序。

我已经填写了这些方法，但我的理解有问题。我认为我的问题是在 bSearch 方法中，因为我无法让它返回除 0 之外的任何东西。我无法让它返回 mid 的新值，这是 key/int 应该的索引被插入。比你的帮助。代码如下:

    static void insertInOrder( int[] arr, int count, int key   )
    {
        int index=bSearch( arr, count, key ); 

        int encodedIndex = -(index+1);
        int decodedIndex = -(index+1);

        for (int i = index; i > 0; i--)
        {
            arr[i] = arr[i-1];
        }

        arr[index]=key; 
    }


    static int bSearch(int[] a, int count, int key)
    {
        int lo = 0;
        int hi = a.length-1;
        int index = 0;
        boolean found = false;
        while (!found && lo <= hi)
        {   
            int mid = lo + ((hi - lo) / 2);
            if (a[mid] == key)
            {
                found = true;
                index = mid;        
            }
            else if (a[mid] > key)
            {
                hi = mid -1;
            }
            else
            {
                lo = mid +1;
            }
        }   
        return index;
    }

Answer 1

您的二进制搜索方法适用于预填充数组。

问题是在插入数组期间，如果数组中不存在该值而不是提供正确的插入位置，则二分查找返回 0。

在这种情况下，您可能需要跟踪数组中当前使用了多少个值。这就是“count”的值(value)所在吗？在这种情况下，您应该从计数而不是最大长度开始您的“hi”值，并且如果您已经到达数组末尾而没有找到值，则需要将计数作为索引返回。

更新:您可以使用此二进制搜索返回插入位置。

    int lo = 0;
    int hi = count-1;
    int index = 0;
    boolean found = false;
    while (!found && lo < hi)
    {
        int mid = lo + ((hi - lo) / 2);
        if (a[mid] == key)
        {
            found = true;
            index = mid;
        }
        else if (a[mid] > key)
        {
            hi = mid;
            index = hi;
        }
        else
        {
            lo = mid +1;
            index = lo;
        }
    }
    return index;