java - 使用递归的随机搜索算法

Question

所以我对算法很陌生，从来没有用递归编程，所以如果我遗漏了一些愚蠢的东西，我提前道歉。

我正在尝试制作一种搜索算法，我认为它的工作方式类似于二进制搜索。

让我们调用正在搜索 x 的元素(比如 x 标记点)

So I search a random index in a sorted array
  If element < x
     lowerbound = index + 1 //to create a sub array
  If element > x
     upperbound = index - 1 //to create a sub array
Repeat process until find x in array.

我遇到的问题是让我的随机数只在范围内搜索。如果我像在我的代码中那样使用 rand.nextInt(upperbound)，它只会一直向左搜索。我需要能够向左或向右搜索它。有没有更好的随机数方法？有谁知道我怎么可能实现这个算法？下面的代码是一天半的工作，老实说，此时我对自己感到非常失望。

另外我知道我还需要考虑我的数组根本不包含 x 的情况，但我想首先对基本搜索机制进行排序。

任何帮助将不胜感激。

private static int counter = 0;

public static int searchRan(int Array[], int x, int low, int up)
{
    counter++;
    Random rand = new Random();
    int select = rand.nextInt(up);
    System.out.println(select);
    if(Array[select] == x)
    {
        System.out.printf("Found %d after %d recursion", x, counter);
        return select;
    }
    else if(Array[select] < x)
    {
        return searchRan(Array, x, select + 1, up);
    }
    else if(Array[select] > x)
    {
        return searchRan(Array, x, low, select - 1);
    }
    else
    {
        return 666;
    }
}

public static void main(String[] args){


    int sortedArray[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int lowerbound = 0;
    int upperbound = sortedArray.length - 1;
    int target = 0;
    System.out.println(searchRan(sortedArray, 0, lowerbound, upperbound));
}

Answer 1

尝试像这样生成你的探测索引:

int select = low + rand.nextInt(up - low + 1);

当low > up时，搜索以失败告终；这应该是您在搜索例程中检查的第一件事。