java - 随机生成的搜索词错误

Question

我正在解决一个问题，涉及生成一定数量的数字(此处名为“Jeff”)并搜索它们，然后记录时间，以便了解使用不同的数字完成任务需要多长时间搜索算法。您将在下面找到到目前为止我所拥有的内容，不包括二进制搜索算法(有效)。我发现的问题是“搜索值”每次都显示为“未找到”。

我采用的代码接受了 Jeff 数量的数字(即用户输入)，然后是用户选择的搜索词。我更改了它，以便随机生成的数字完全填满列表，但这使搜索无法工作。或者看起来就是这样。

一切都有帮助!

谢谢!

public static void main(String[] args) {

    long startTime = System.nanoTime();

    int Jeff = 20;

    List<Integer> intList = new ArrayList<Integer>(Jeff);
    int searchValue = 0, index;
    int temp;

    Random generator = new Random();

    System.out.println("Entering " + Jeff + " numbers...");
    //Adds unique values up to and through Jeff
    while (intList.size() < Jeff) {
            Integer next = generator.nextInt(Jeff) + 1;
            if (!intList.contains(next))
            {
                // Done for this iteration
                intList.add(next);
            }
    }
    System.out.println("List: " + intList);

    //Adding to ArrayList
    for (int i = 0; i < intList.size(); i++) {
        temp = generator.nextInt(Jeff) + 1;
        intList.set(i,temp);
    }
    System.out.print("Enter a number to search for: ");
    searchValue = generator.nextInt(Jeff) + 1;
    System.out.println(searchValue);

    index = binarySearch(intList, searchValue);

    if (index != -1) {
        System.out.println("Found at index: " + index);
    } 
    else {
        System.out.println("Not Found");
    }

    long endTime = System.nanoTime();
    long duration1 = endTime - startTime;
    System.out.println(duration1);
    }
  static int binarySearch(List<Integer> intList, int find) {
    long startTime2 = System.nanoTime();
    int start, end, midPt;
    start = 0;
    end = intList.size() - 1;
    while (start <= end) {
        midPt = (start + end) / 2;
        if (intList.get(midPt) == find) {
            long endTime2 = System.nanoTime();
            long duration2 = endTime2 - startTime2;
            System.out.println(duration2);
            return midPt;
        } else if (intList.get(midPt) < find) {
            start = midPt + 1;
        } else {
            end = midPt - 1;
        }
    }
    long endTime2 = System.nanoTime();
    long duration2 = endTime2 - startTime2;
    System.out.println(duration2);
    return -1;
    }
}

Answer 1

您正在用随机数字填充列表。不幸的是，这对于二分搜索来说效果不太好。

例如，想象一下 Jeff = 5 。添加随机数后，您的列表可能如下所示:

[3, 1, 5, 2, 4]

现在，如果您搜索 2，您首先查看列表中点的元素 5。由于 2 小于 5，因此您继续在列表的左半部分查找它(即 [3, 1] )。显然，它不存在，因此您的搜索将失败。

您需要首先对列表进行排序(不幸的是，这使得解决方案变得微不足道)，或者选择一个新的搜索策略。对于排序列表上的重要搜索，您可以搜索不限于 1 <= n <= Jeff 的整数排序列表。

<小时/>

附注请不要将您的变量称为“Jeff”。这可能有点可爱，但这也不是一个好习惯，因为它会妨碍可读性。