使用二进制搜索在正确索引处的数组中打开 space

Question

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

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

这些方法我都填过了，但是我的理解有问题。我认为我的问题是在 bSearch 方法中，因为除了 0 之外我无法将它设置为 return。我无法将它设置为 return mid 的新值，即索引应该插入键/ 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

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

问题是在插入数组期间，如果数组中不存在该值而不是提供正确的插入位置，则二进制搜索 returns 0。

在这种情况下，您可能需要跟踪数组中当前使用了多少个值。那是值 "count" 的用途吗？在这种情况下，您应该从计数而不是最大长度开始您的 "hi" 值，并且如果您已到达数组末尾但未找到值，则需要将 return 计数作为索引。

更新：您可以使用此二进制搜索到 return 插入位置。

    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;

使用二进制搜索在正确索引处的数组中打开 space

Using Binary Search to open up a space in an array at the correct index

java

arrays

if-statement

binary-search

while-loop