Binary Search Implementation

Question

I want to implement a Binary Search and I have three methods for that. I want to output the amount of recursive calls needed for a specific factor.

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.

I don't know how to call a specific element of the list haystack. How should I implement the three methods of the class BinarySearch correctly and how should I implement the main class for the input of a number and the amount of recursive calls?

Here is the 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()*/;
    }
}

Here is the main 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();
    }
}

Tell me if you need both Interfaces and the class Unit, but in the class BinarySearch I have the same constructor.

Answer 1

This is a possible solution:

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 2

I got told that if I want to access the central element of the haystack, I need to write the following line:

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

Now the thing is to get it compared with needle which has the type Key. Because when this works, I just need to compare the searched element with the central element of the haystack, then if the searched element is smaller than mid_unit, I set the right limit to

right = middle;

where

middle = (left + right) / 2;

and then

else left = middle;

Answer 3

Here we have one search operation that is supposed to generate two outputs 1. value found 2. count.

I think two approaches can be tried :-

1. BinarySearch can have instance variables for factor, list or haystack, key and count. To do a search first create an instance of BinarySearch with constructor that takes list and key. Call setFactor() to set factor. Call doSearch() or find with no arguments that runs on list, key instance variables and return value. While running doSearch() increment count instance variable for each recursive call. once doSearch() returns a value , call getCount() to get the number of recursive calls. With this, for each search to be done new instance of BinarySearch should be created.

2. Instead of returning value from find , return response object that contains count and value if found or null . While starting search create the response object with count 0 and object null. Pass response object with every recursive call. At start of each recursive call increment count and return the response object once when value is found. getNumberOfCalls() should be defined in the response and be called once find returns the response.