Блог

Я пытаюсь написать программу, которая выполняет последовательный поиск и двоичный поиск в массиве с именем, items который имеет 10000 отсортированных случайных int значений. Второй вызванный массив targets загружается с 1000 int значениями (500 значений из items массива и 500 значений, которых нет в items массиве).

В принципе, поиск должен проходить через массив items, чтобы искать int значения в targets массиве. Это мой код:

   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) amp;amp; (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) amp;amp; (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 миллисекунд

Ваш sequentialSearch полностью неверен, вы даже не обращаетесь к массиву в нем.

Оба ваших метода поиска вызывают loadItemsAndTargets. Он должен быть вызван только один раз

BinarySearch работает только с отсортированным массивом. Ваши массивы не отсортированы.

Даже если вы исправите все эти ошибки. Остерегайтесь, что ваш массив будет содержать дубликаты. Итак, если попытаться сравнить индекс между sequentialSearch и BinarySearch, они могут не совпадать, если ваш BinarySearch не вернет нижнюю границу

Иногда легче писать код, когда вы хорошо разбираетесь в методах поиска под рукой. Имея это в виду, я повторю то, что вы, вероятно, слышали, на случай, если это не было хорошо объяснено.

Последовательный поиск прост:

 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.
  

Двоичный поиск также прост:

 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.
  

Преимущество последовательного поиска в том, что ваш элемент в конечном итоге будет найден, даже если список не отсортирован. Преимущество двоичного поиска в том, что вы найдете нужный элемент намного быстрее, но список должен быть отсортирован. Например, для поиска элемента в списке из миллиона элементов с помощью последовательного поиска потребуется в среднем полмиллиона сравнений; но двоичный поиск займет всего около двадцати сравнений. Это потому, что каждое сравнение в двоичном поиске отбрасывает половину оставшихся возможностей, в то время как каждое сравнение в последовательном поиске отбрасывает только одну возможность.