Computer Science Canada Binary Search Base Case help |
| Author: | 2sticks [ Tue Oct 24, 2017 7:13 pm ] |
| Post subject: | 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? |
|
| Author: | Insectoid [ Wed Oct 25, 2017 9:28 am ] |
| Post subject: | RE:Binary Search Base Case help |
What happens to min and max as the tree progresses in the search? |
|