Двоичные / последовательные поиски

Question

Я пытаюсь написать программу, которая выполняет последовательный поиск и двоичный поиск в массиве с именем items, который имеет 10000 отсортированных случайных значений int.Второй массив с именем targets загружается со значениями 1000 int (500 значений из массива items и 500 значений, которых нет в массиве 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) && (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 не вернет нижнюю границу

Answer 2

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

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

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.

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