0

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

基本上,搜索需要通过 items 数组来查找数组中的inttargets。这是我的代码:

  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毫秒

4

2 回答 2

2

您的顺序搜索全错了,您甚至没有访问其中的数组。

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

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

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

于 2011-11-09T04:12:10.490 回答
1

Sometimes it is easier to write the code when you have a very strong grasp of the searching techniques at hand. With that in mind, I'll repeat what you probably have heard just in case it wasn't explained well.

A sequential search is simple:

1. Set the starting index just before the beginning.
2. If there is a "next" item, check the next item to see if it matches.  
2a. If it does match you found the item in your collection.
2b. If it does not match update the starting index to the item you just checked and continue at step 2.
3. If there is no next item, then you searched everything without finding your item.

A binary search is also simple:

1. If the unsearched part of your list is empty, then determine you didn't find the item.
2. If the unsearched part of your list is just one element, then check the element to see if it matches the lookup item.
2a. If id does match, you found the item in your list.
2b. If it does not match, the item isn't in your list.
3. If the unsearched part of your list is more than one element, find the element closest to the middle. It is ok to divide two element lists like {2, 4} into {2} 4 {} where 4 is the middle.
3a. If the middle matches the lookup item, you found the item in your list.
3b. If the middle is larger than the lookup item, select the "smaller" side list and repeat the process.
3c. If the middle is smaller than the lookup item, select the "larger" side list and repeat the process.

The advantage of a sequential search is that your item will eventually be found, even if the list is not sorted. The advantage of a binary search is that you will find your item much faster but the list must be sorted. For example, a million item list will take on average half a million comparisons to find an item by sequential search; but, a binary search will take only about twenty comparisons. That is because each comparison in a binary search throws away half of the remaining possibilities while each comparison in a sequential search only throws away one possibility.

于 2011-11-09T04:36:12.390 回答