使用二进制搜索以正确的索引打开数组中的空格-Java 学习之路

我应该创建两个方法：第一个方法，bSearch，是一个二进制搜索算法 . 第二个方法insertInOrder应该从bSearch方法中获取索引，并在数组中找到该索引，通过将该数组的所有其他元素移位，在该索引处打开一个点，然后插入key / int那个指数 .

将从包含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;
    }

1 回答

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

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

在这种情况下，您可能需要跟踪阵列中当前使用的值的数量 . 这是“计数”的 Value 是什么？在这种情况下，您应该在count而不是max length处开始“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;
```
回复于 2024-04-27T21:25:29+08:00

使用二进制搜索以正确的索引打开数组中的空格

1 回答

相关问题