随机二进制搜索算法-Java 学习之路

下面的算法应该是二元搜索的变体，而不是选择中间选择和比较随机索引 . 该算法渐渐变差，但这只是一项任务 . 该算法考虑了当随机索引i处的元素等于搜索值时的情况，在这种情况下它返回true，而第二种情况是当索引i处的元素大于搜索值时，在这种情况下我们递归地调用搜索在i - 1的输入n上 . 如果元素总是大于或等于搜索值，那么算法工作正常 .

然而，当随机索引处的元素小于搜索值时会发生什么？直观地，我认为输入n应该增加i 1，即使检查n是否大于数组大小，我似乎得到stackoverflows ..

public static boolean search(int[] keys, int value, int n) {
    if(n <= 0 || n > keys.length) 
        return false;
    else {
        Random random =   new Random();
        int i       =   random.nextInt(n);

        if(keys[i] == value) 
            return true;
        else if(keys[i] > value) 
            return search(keys, value, i - 1);
        else 
            return search(keys, value, i + 1);
    }
}

2 回答

2
看到你的代码的这一部分，
```
else if(keys[i] > value) 
     return search(keys, value, i - 1); //Line1
 else 
     return search(keys, value, i + 1); //Line2
```
在这两种情况下，您都在搜索数组的相同部分 .

Line1 从 0 到 i - 1 搜索数组中的 value .
Line2 从 0 到 i + 1 搜索数组中的 value .

你应该做的是，

Line1 应从 0 到 i - 1 搜索数组中的 value .
Line2 应该从 i + 1 到数组末尾搜索数组中的 value .
回复于 2024-04-24T15:47:21+08:00

您的代码根本就是错误的（我认为） . 根据你的说法（你的问题陈述中的条件），这应该是代码：

public static boolean search(int[] keys, int value, int l, int r)
{
    if(l < 0 || r >= keys.length || l>r) return false;
    else
    {
        Random random =   new Random();
        int i       =   l + random.nextInt(r-l);

        if(keys[i] == value) return true;
        else if(keys[i] > value) return search(keys, value, l, i - 1);
        else return search(keys, value, i + 1, r);
    }
}

回复于 2024-04-24T15:47:21+08:00

随机二进制搜索算法

2 回答

相关问题