下面的算法应该是二分搜索的变体,它不是选择中间值,而是选择并比较随机索引。该算法渐近变差,但这只是一项任务。该算法考虑当随机索引 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);
}
}
最佳答案
您的代码根本上是错误的(我认为)。根据你所说的(你的问题陈述中的条件),这应该是代码:
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);
}
}
关于java - 随机二分搜索算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32471924/