0

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

我采用了接受 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;
    }
}
4

2 回答 2

1

你正在用随机数填充你的列表。不幸的是，这对于二分搜索效果不佳。

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

[3, 1, 5, 2, 4]

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

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

PS请不要将您的变量称为“杰夫”。这可能有点讨人喜欢，但也不是一个好习惯，因为它妨碍了可读性。

于 2013-04-11T03:32:51.333 回答
0

您确定 searchValue 在 intList 中吗？看起来应该是

searchValue = intList.get(generator.nextInt(intList.size()));
于 2013-04-11T03:25:19.113 回答