-----------------------------------

2sticks

Tue Oct 24, 2017 7:13 pm


Binary Search Base Case help

-----------------------------------

import java.io.*;
import java.util.*;
import java.text.*;

public class binarySearch
{

    static final int MAX = 1500; // 1500 Records

    //Linear Search void Method
    static void linearSearch (String[] phoneBook) throws IOException
    {
        String search;

        int counter = 0; // A counter for the number of comparisons made

        BufferedReader stdin = new BufferedReader (new InputStreamReader (System.in));
        System.out.println ("Enter the phone number to be searched for: "); // Get the requested number
        search = stdin.readLine ();

        for (int i = 0 ; i < MAX ; i++)
        {
            counter++;
            if (phoneBook [i].equals (search)) //If linear search method found the number
            {
                System.out.println ("The phone number was found at Index number: " + i);
                System.out.println ("There were " + counter + " comparisons made.");
                break;
            }


        }
        if (counter == 1500) //Linear search did not find the number
        {

            System.out.println ("Your number was not found in the phonebook");
            System.out.println ("There were " + counter + " comparisons made.");

        }
    }


    //Binary Search void Method
    public static int binarySearchMethod (String[] phoneBook, String search, int min, int max, int count) throws IOException
    {
        BufferedReader stdin = new BufferedReader (new InputStreamReader (System.in));

        count++; // Count the number of comparisons

        int mid = (min + max) / 2;

        if (phoneBook [mid].compareTo (search) > 0)
            return binarySearchMethod (phoneBook, search, min, mid, count);

        else if (phoneBook [mid].compareTo (search) < 0)
            return binarySearchMethod (phoneBook, search, mid, max, count);

        if (mid == 1)
        System.out.println ("Not found");
        return 0;
        
    }


    public static void main (String str[]) throws IOException
    {
        BufferedReader stdin = new BufferedReader (new InputStreamReader (System.in));
        DecimalFormat df = new DecimalFormat ("#");
        String phoneNumber, searchOption;
        String line;
        int counter = 0;
        int select;

        BufferedReader reader = new BufferedReader (new FileReader ("phone.txt"));

        String[] phoneBook = new String [MAX]; //"Phone book" array

        //Inputs all the records from the text file and stores it into an array
        while ((line = reader.readLine ()) != null)

            {
                phoneBook [counter] = line;
                counter++;
            }


        reader.close ();


        System.out.println ("How would you like to search for the phone number? \n 1)Linear Search \n 2)Binary Search");
        select = Integer.parseInt (stdin.readLine ());


        //Choice of method of searching
        switch (select)
        {
            case 1: //Linear

                linearSearch (phoneBook);

                break;

            case 2: //Binary
                String search;
                System.out.println ("Enter the phone number to be searched for: ");
                search = stdin.readLine ();
                int count = 0;
                int position = binarySearchMethod (phoneBook, search, 0, MAX - 1, count);
                
                
                System.out.println ("Search term is at: " + position + "\n Number of comparisions: " + count);

                break;

                // A form of validation if the user does not pick one of the options
            default:
                System.out.println ("Pick again");
                break;


        }
    }
}




The stuff above is the code, how would I add for a base case in the binary search method to stop the infinite loop if there is no number present in the array. Also why is the count++ not working as well?


-----------------------------------

Insectoid

Wed Oct 25, 2017 9:28 am


RE:Binary Search Base Case help

-----------------------------------

What happens to min and max as the tree progresses in the search?