二进制搜索实现

Question

我想实现二进制搜索，我有三种方法。我想输出特定因素所需的递归调用量。

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.

我不知道如何调用列表 haystack 的特定元素。 class BinarySearch 的三个方法应该如何正确实现，主要的class 输入数字和递归调用量应该如何实现？

这是 class 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()*/;
    }
}

这里是主要的class:

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();
    }
}

如果您同时需要接口和 class 单元，请告诉我，但在 class BinarySearch 中，我有相同的构造函数。

Answer 1

这里我们有一个搜索操作应该生成两个输出 1。value 找到 2。count。

我认为可以尝试两种方法:-

BinarySearch 可以有 factor、list 或 haystack、key 和 count 的实例变量。要进行搜索，首先使用采用 list 和 key 的构造函数创建 BinarySearch 的实例。调用 setFactor() 设置因子。调用不带参数的 doSearch() 或 find，在 list、key 实例变量和 return 值上运行。而运行 doSearch() 为每个递归调用递增 count 实例变量。一旦 doSearch() returns a value ，调用 getCount() 得到递归调用的次数。有了这个，对于每个要完成的搜索，应该创建 BinarySearch 的新实例。
而不是 returning value 来自 find ， return response 包含 count 和 value 如果找到或 null 。开始搜索时，创建计数为 0 且对象为 null 的响应对象。在每次递归调用时传递响应对象。在每个递归调用开始时递增计数和 return 找到值时响应对象一次。 getNumberOfCalls() 应在 response 中定义并在 find return 中调用一次 response.

Answer 2

有人告诉我，如果我想访问 haystack 的中心元素，我需要编写以下行：

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

现在的问题是将它与具有 Key 类型的针进行比较。因为当这个工作时，我只需要将搜索到的元素与大海捞针的中心元素进行比较，然后如果搜索到的元素小于mid_unit，我将右限制设置为

right = middle;

哪里

middle = (left + right) / 2;

然后

else left = middle;

Answer 3

这是一个可能的解决方案：

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;
    }
}

二进制搜索实现

Binary Search Implementation

java

implementation

abstract-class

class

binary-search