Реализация бинарного поиска

Question

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

Коэффициент два означает, что пространство поиска делится на половину на каждом шаге рекурсии. * Коэффициент три означает, что пространство поиска делится на одну треть и две трети на каждом шаге рекурсии. * В каждом случае предполагается целочисленное деление, что означает, что дроби округляются в меньшую сторону.

Я не знаю, как назвать конкретный элемент списка стогом сена. Как правильно реализовать три метода класса BinarySearch и как реализовать основной класс для ввода числа и количества рекурсивных вызовов?

Вот класс BinarySearch:

package u8a1;

import java.util.List;

public class BinarySearch<Key extends Comparable<Key>, Value> implements IBinarySearch<Key, Value>, IMeasure {

    public Key key;

    public Value value;

    public BinarySearch() {
        this.key = key;
        this.value = value;
    }
    public Value find(List<Unit<Key, Value>> haystack, Key needle)
    {
        //return haystack.isEmpty() ? null : haystack.get(0).value;
        int m, li, re;
        li = 0;
        re = haystack.size();
        //if ()
        return value;
    }
    /** 
 * Set the factor for the binary search.
 * 
 * A factor of two means that the search space is split into half-half in each recursion step.
 * A factor of three means that the search space is split into one third and two thirds in each recursion step.
 * In each case integer division is assumed, which means fractions are rounded down.
 * 
 * This method is called first after instantiation.
 * 
 * @param factor
 *            an integer value
 */
    public void setFactor(int factor)
    {
        //int m, li, re;
        //li = 0; re = haystack.size();
        //getNumberofCalls()
        return;
    }
    public int getNumberofCalls()
    {
        return 1/* + getNumberofCalls()*/;
    }
}

Вот основной класс:

package u8a1;

/**
 * Main class of the Java program. 
 * 
 */
import java.util.Scanner;

//...
class Scan{
    Scanner in = new Scanner(System.in);
    int num = in.nextInt();
}


public class Main {

    public static void main(String[] args) {

        // we print a heading and make it bigger using HTML formatting
        System.out.println("<h4>-- Binaere Suche --</h4>");
        int anzahl = 0;
        //zahl.Scan();
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
    }
}

Скажите, нужны ли вам оба интерфейса и класс Unit, но в классе BinarySearch у меня один и тот же конструктор.

Answer 1

Мне сказали, что если я хочу получить доступ к центральному элементу стога сена, мне нужно написать следующую строку:

Unit<Key, Value> mid_unit = haystack.get(middle);

Теперь нужно сравнить его с иглой с ключом типа. Поскольку, когда это работает, мне просто нужно сравнить искомый элемент с центральным элементом стога сена, тогда, если искомый элемент меньше, чем mid_unit, я устанавливаю правильный предел на

right = middle;

где

middle = (left + right) / 2;

, а затем

else left = middle;

Answer 2

Это возможное решение:

package u8a1;

import java.util.List;
import java.util.ArrayList;

public class BinarySearch<Key extends Comparable<Key>, Value> implements IBinarySearch<Key, Value>, IMeasure {

    private int dividedBy = 2;

    private int numOfCall = 1;

    public Key key;

    public Value value;

    public BinarySearch() {
        this.key = key;
        this.value = value;
    }
    public Value find(List<Unit<Key, Value>> haystack, Key needle)
    {
        if (haystack.size() == 0) return null;
        if (needle.compareTo(haystack.get(haystack.size()/dividedBy).key) == 0) return haystack.get(haystack.size()/dividedBy).value;
        if (haystack.size() == 1) return null;
        else if(needle.compareTo(haystack.get(haystack.size()/dividedBy).key) > 0)
        {
            ++numOfCall;
            return find(haystack.subList((haystack.size()/dividedBy), haystack.size()), needle);
        }
        else if(needle.compareTo(haystack.get(haystack.size()/dividedBy).key) < 0)
        {
            ++numOfCall;
            return find(haystack.subList(0, (haystack.size()/dividedBy)), needle);
        }
        else return null;
    }
    public void setFactor(int factor)
    {
        dividedBy = factor;
    }
    public int getNumberofCalls()
    {
        return numOfCall;
    }
}

Answer 3

Здесь у нас есть одна операция поиска, которая должна сгенерировать два выхода 1. value найдено 2. count.

Я думаю, что можно попробовать два подхода: -

1. BinarySearch может иметь переменные экземпляра для фактора, списка или стога сена, ключа и счетчика. Для поиска сначала создайте экземпляр BinarySearch с конструктором, который принимает list и key. Звоните setFactor(), чтобы установить коэффициент. Вызовите doSearch() или find без аргументов, работающих с list, key переменными экземпляра и возвращаемым значением. При выполнении doSearch() инкремент count переменная экземпляра для каждого рекурсивного вызова. как только doSearch() вернет value, позвоните getCount(), чтобы узнать количество рекурсивных вызовов. При этом для каждого поиска должен быть создан новый экземпляр BinarySearch.

2. Вместо того, чтобы возвращать value из find, вернуть response объект, который содержит count и value, если найден или равен нулю. В начале поиска создайте объект ответа со счетчиком 0 и нулевым объектом. Передавать объект ответа при каждом рекурсивном вызове. При запуске каждого рекурсивного вызова увеличивают счетчик и возвращают объект ответа один раз, когда значение найдено. getNumberOfCalls() должен быть определен в response и вызываться один раз find возвращает response.