java - 二分/顺序搜索

Question

我正在尝试编写一个程序，在名为 items 的数组中进行顺序搜索和二分搜索，该数组具有 10000 个已排序的随机 int 值。第二个名为 targets 的数组加载了 1000 个 int 值(500 个来自 items 数组的值和 500 个不在 items 数组)。

基本上，搜索需要遍历 items 数组来查找 targets 数组中的 int 值。这是我的代码:

  import java.util.*;

 // Loads two arrays with integers
 // Searches the arrays using sequential search and binary search
 // Compares the time for each search

public class Searches {

private int items[], targets[];

public Searches() { 

    this.items = new int[10000];
    this.targets = new int[1000];
}

public void loadItemsAndTargets(){

    int nextValue = 100;
    int index = 0;

    Random generator = new Random(1); 

    items[0] = nextValue;

    /* load the items array with items to be searched through */

    for (index = 1; index < items.length; index++){
        nextValue = nextValue + generator.nextInt(100);
        items[index]= nextValue;
    }

    /* load the targets array with target values that will be searched for within
     * array items, and target values that are not within array items
     */

    index = 0;

    while (index < targets.length){
        targets[index] = items[index*10];
        targets[index+1] = generator.nextInt(100);
        index = index + 2;
    }      
}

public int sequentialSearch(int target) {
    /* Using the sequential search algorithm, search the items array for the target value passed
     * If found, return the index in the items array, otherwise return -1
     */
    this.loadItemsAndTargets();

    int key = target;
    int index;

    boolean found = false;

    index = 0;
    while ((!found) && (index < items.length)) 
        if (key == target)
            found = true;
        else
            index = index + 1;

    if (!found) 
        index = -1;
    return index;
}       

public int binarySearch(int target){
    /* Using the binary search algorithm, search the items array for the target value passed
     * If found, return the index in the items array, otherwise return -1
     */
    this.loadItemsAndTargets();


    target = targets.length;
    int key = target;
    boolean found = false;
    int guess = 0;
    int low = 0;
    int high = items.length - 1;
    while ((!found) && (low < high)) {
        guess = (high+low)/2;
        if (key == items[guess]) 
            found = true;
        else if (key < items[guess])
            high = guess - 1;
        else
            low = guess + 1;

        if (!found)
            return - 1;
    }

   return guess;
}
public static void main(String[] args) {
    int index = 0;
    Searches searcher = new Searches();
    searcher.loadItemsAndTargets();

    /* call the method that searches array items 
     * for each of the values in array targets
     * using the sequential search algorithm
     * print the approximate elapsed time in milliseconds
     * For the FIRST FIVE searches print out the index 
     * where target value was found or print -1 if it was not found 
     */


    long startTimeSequential;
    startTimeSequential  = System.currentTimeMillis();

    System.out.println(searcher.sequentialSearch(index));

    long endTimeSequential;
    endTimeSequential = System.currentTimeMillis();

    long totalTimeSequential;
    totalTimeSequential = endTimeSequential-startTimeSequential;
    System.out.println("sequential search time: " + totalTimeSequential + " milliseconds");

    /* call the method that searches array items
     * for each of the values in array targets
     * using the binary search algorithm
     * print the approximate elapsed time in milliseconds
     * For the FIRST FIVE searches print out the index 
     * where target value was found or print -1 if it was not found 
     */
    long startTimeBinary;
    startTimeBinary = System.currentTimeMillis();

    System.out.println(searcher.binarySearch(index));

    long endTimeBinary;
    endTimeBinary = System.currentTimeMillis();

    long totalTimeBinary;
    totalTimeBinary = endTimeBinary - startTimeBinary;
    System.out.println("binary search time: " + totalTimeBinary + " milliseconds");
 }      
}   

编辑:输出应该是这样的>

395

986

-1

14

-1

顺序搜索时间:40毫秒

395

986

-1

14

-1

二分查找时间:0毫秒

Answer 1

您的sequentialSearch完全错误，您甚至没有访问其中的数组。

您的搜索方法都调用loadItemsAndTargets。它应该只被调用一次

binarySearch 仅适用于排序数组。您的数组未排序。

即使您纠正了所有这些错误。请注意，您的数组将包含重复项。因此，如果尝试比较 sequentialSearch 和 binarySearch 之间的索引，它们可能不匹配，除非您的 binarySearch 返回下限