12 Replies - 3893 Views - Last Post: 09 September 2012 - 01:07 PM Rate Topic: -----

#1 scy0846  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 68
  • Joined: 03-October 11

I need to create a count of probes in my binary search.

Posted 08 September 2012 - 11:46 AM

Ok I thought I know I have the binary search correct. I created an int probe that is supposed to show the probecount, but the search terms are...
California
MS
Texas
Hwai
California
Indiana
Okalahooma
Florida
Hawaii
Alabam
Alabama
Puerto_Rico
FL
New_York


The issue I come across is California is submitted twice. I should get the same count for it, but I get...

BINARY SEARCH RESULTS

Found California.
2 Probes

MS not found..
2 Probes

Found Texas.
4 Probes

Hwai not found..
4 Probes

Found California.
6 Probes

Found Indiana.
7 Probes

Okalahooma not found..
7 Probes

Found Florida.
9 Probes

Found Hawaii.
10 Probes

Alabam not found..
10 Probes

Found Alabama.
12 Probes

Puerto_Rico not found..
12 Probes

FL not found..
13 Probes

Found New_York.
15 Probes

My code...
 public void binarySearch()
    {
        System.out.println("\n\n\n BINARY SEARCH RESULTS");
        int probe=0;
        for(int curIn=0; curIn<numKeys; curIn++)
        {
            probe++;
            String key = myKeys[curIn];
            int index =binarySearch(key);
            
            if(index!=-1)
            {
                System.out.println(" \nFound "+key + ".\n" + (probe + 1) + " Probes");
            }
            else
            {
                System.out.println(" \n" + key + " not found." + ".\n" + probe + " Probes");
            }
        }
    }
//------------------------------------------------------------------------------
private int binarySearch(String key) 
{
   int lo = 0;
   int hi = numStates -1;
   int curIn;
   while(lo <= hi)
   {
      curIn=lo+(hi - lo)/2;
      if(myStates[curIn].getStateName().compareTo(key)>0)
      {
          hi=curIn-1;
      }
      else if(myStates[curIn].getStateName().compareTo(key)<0)
      {
          lo=curIn+1;
      }
      else 
      {
          return curIn;
      }
   }
   return -1;
}


Is This A Good Question/Topic? 0
  • +

Replies To: I need to create a count of probes in my binary search.

#2 lnc12  Icon User is offline

  • D.I.C Regular

Reputation: 1
  • View blog
  • Posts: 268
  • Joined: 21-May 08

Re: I need to create a count of probes in my binary search.

Posted 08 September 2012 - 01:34 PM

Is your myStates array just a string array ?
Was This Post Helpful? 0
  • +
  • -

#3 scy0846  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 68
  • Joined: 03-October 11

Re: I need to create a count of probes in my binary search.

Posted 08 September 2012 - 01:53 PM

It's an object. here's the rest of the code if it helps.

package Project1Mitchell;

import java.io.*;

/**
 *
 * @author Taylor Mitchell
 */
public class StateController 
{

    private State[] myStates;
    private int numStates = 0;
    private String[] myKeys = new String[14];
    private int numKeys;
    public int swapCount;
    private boolean swap;

    /**
     * Creates a new state object
     *
     */
    public StateController(int maxSize) 
    {
        myStates = new State[maxSize];
    } // end stateController()

    /**
     * Routine for loading data into the array of States
     *
     */
    public void loadData(String filename) throws IOException 
    {
        FileInputStream fis1 = new FileInputStream("statearray.txt");
        BufferedReader br1 = new BufferedReader(new InputStreamReader(fis1));
        int regnum, pop;
        String name, cap, abbr, reg;

        String inputString;
        inputString = br1.readLine();

        System.out.printf("%15s %15s %5s %12s %17s %5s",
                "Name", "Capital", "Abbr", "Population", "Region   ", "Region Number");
        System.out.println("\n----------------------------------------------------------------------------------");

        while (inputString != null) 
        {
            name = inputString.substring(0, 15).trim();
            cap = inputString.substring(15, 30).trim();
            abbr = inputString.substring(30, 32).trim();
            pop = Integer.parseInt(inputString.substring(32, 40).trim());
            reg = inputString.substring(40, 55).trim();
            regnum = Integer.parseInt(inputString.substring(55, 56).trim());

            myStates[numStates] = new State(name, cap, abbr, pop, reg, regnum);
            numStates++;
            inputString = br1.readLine();
        } // end while (inputString != null) 
        br1.close();
    }//end loadData(String filename) throws IOException

    public void displayStates() 
    {
        int index;
        for (index = 0;
                index < numStates;
                index++) 
        {
            System.out.println(myStates[index]);
        }//end for loop
    }//end displayStates()

    /**
     *
     */
    public void sort() 
    {
        int in, out, min;
        swapCount=0;
        for (out = 0;
                out < (numStates-1);
                out++) 
        {
            min = out;
            for (in = out + 1;
                    in < numStates;
                    in++) 
            {
                if (myStates[in].getStateName().compareTo(myStates[min].getStateName()) < 0) 
                {
                    min = in;
                    swap = true;
                }//end if (...)  
            }//end inner for loop
            if(swap)
            {
                swap(out, min);
                swap = false;
            }//end if(swap)                   
        }//end outer for loop 
        System.out.println("\n\n\t\t\t\tSorted States");
        System.out.printf("%15s %15s %5s %12s %17s %5s",
                "Name", "Capital", "Abbr", "Population", "Region   ", "Region Number");
        System.out.println("\n----------------------------------------------------------------------------------");
        displayStates();
    }//end sort()

    private void swap(int one, int two) 
    {
        State name = myStates[one];
        myStates[one] = myStates[two];
        myStates[two] = name;
        swapCount++;
    }//end swap(int first, int next)
    
    public void getCount()
    {
        System.out.println("\nIt took " + swapCount  + " exchanges to sort\n");
    }

    public void loadSearchKeys(String filename) throws IOException 
    {
        FileInputStream fis1 = new FileInputStream("search.txt");
        BufferedReader br1 = new BufferedReader(new InputStreamReader(fis1));
        int end;
        String key;

        String inputString;
        inputString = br1.readLine();

        while (inputString != null) 
        {
            end = Math.min(14, inputString.length());
            key = inputString.substring(0, end);
            myKeys[numKeys] = key;
            numKeys++;
            inputString = br1.readLine();
        } // end while
        br1.close();
    }//end loadSearchKeys(String filename) throws IOException

    public void displayKeys() 
    {
        for (int index = 0;
                index < numKeys;
                index++) 
        {
            System.out.println(myKeys[index]);
        }//end for loop
    }//end displayKeys()

    public void search() 
    {
        System.out.println("\nLINEAR SEARCH RESULTS");
        int index, probe;

        for (index = 0;
                index < numKeys;
                index++) 
        {
            for (probe = 0;
                    probe < numStates;
                    probe++) 
            {
                if (myStates[probe].getStateName().equals(myKeys[index])) {
                    break;
                }
            }//end inner for loop
            if (probe == numStates) 
            {
                System.out.println("\nCan not find " + (myKeys[index]) + ".\n" + probe + " Probes");
            }//end if (probe == numStates)
                else 
            {
                    System.out.println("\nFound " + (myKeys[index]) + ".\n" + (probe + 1) + " Probes");
            }//end else
        }//end outer for loop
    }//end search()

     public void binarySearch()
        {
            System.out.println("\n\n\n BINARY SEARCH RESULTS");
            int probe=0;
            for(int curIn=0; curIn<numKeys; curIn++)
            {
                probe++;
                String key = myKeys[curIn];
                int index =binarySearch(key);

                if(index!=-1)
                {
                    System.out.println(" \nFound "+key + ".\n" + (probe + 1) + " Probes");
                }//end if(index!=-1)
                else
                {
                    System.out.println(" \n" + key + " not found." + ".\n" + probe + " Probes");
                }//end else
            }//end for(int curIn=0; curIn<numKeys; curIn++)
        }//end binarySearch()

    private int binarySearch(String key) 
        {
           int lo = 0;
           int hi = numStates -1;
           int curIn;
           while(lo <= hi)
           {
              curIn=lo+(hi - lo)/2;
              if(myStates[curIn].getStateName().compareTo(key)>0)
              {
                  hi=curIn-1;
              }//end if(myStates[curIn].getStateName().compareTo(key)>0)
              else if(myStates[curIn].getStateName().compareTo(key)<0)
              {
                  lo=curIn+1;
              }//end else if(myStates[curIn].getStateName().compareTo(key)<0)
              else 
              {
                  return curIn;
              }//end else
           }//end while(lo <= hi)
           return -1;
        }//end binarySearch(String key)
}//end StateController()




The code for class State is

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Project1Mitchell;
/**
	This class is to show what a State object is
*/  
	public class State
	{
            private int regionNumber;
            private int statePopulation;
            private String stateName;
            private String stateCapital; 
            private String stateAbbreviation; 
            private String stateRegion;

            
    public State (String name, String cap, String abbr, int pop, String reg, int regNum)
    {
	stateName = name;	
	stateCapital = cap;
        stateAbbreviation = abbr;
        statePopulation = pop;
        stateRegion = reg;
        regionNumber = regNum;

    }// end State
    
    	public String getStateName()
	{
		return stateName;
	}//end getStateName


	public String getStateCapital()
	{
		return stateCapital;
	}//end getStateCapital


        public String getStateAbbreviation()
        {
                return stateAbbreviation;
        }//end getStateAbbreviation

        public String getStateRegion()
        {
                return stateRegion;
        }//end getStateRegion
        
        public int getRegionNumber()
        {
                return regionNumber;
        }//end getRegionNumber
	
        public int getStatePopulation()
        {
                return statePopulation;
        }//end getStatePopulation()

            @Override
    public String toString()
    {
		String str = String.format("%15s %15s %5s %12d %17s %5d", 
                         stateName, stateCapital, stateAbbreviation, statePopulation, stateRegion, regionNumber);
                return str;
	}// end toSTring()
        }// end State() constructor





The Main class

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Project1Mitchell;

import java.io.*;

/**
 *
 * @author Taylor
 */
public class Main 
{

    public static void main (String[] args) throws IOException
	{
		// create an array of individual state objects to hold 50 items
		StateController myStateController;
		myStateController = new StateController (50);

		// Call method to retrieve data and store it in the new array
		myStateController.loadData ("statearray.txt");

		//  display Original array of stated with a header
		myStateController.displayStates();
                
                //sorts state objects
                myStateController.sort();
                
                myStateController.getCount();
                
                //obtains search keys from file search.txt
		myStateController.loadSearchKeys("search.txt");
                
                //linear search
                myStateController.search();
                
                //binary search
                myStateController.binarySearch();
	}// end main()
} // end class



Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8332
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: I need to create a count of probes in my binary search.

Posted 08 September 2012 - 07:10 PM

Your probe is just counting the number of different searchs you are doing
not the number of probes for each search
Was This Post Helpful? 0
  • +
  • -

#5 scy0846  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 68
  • Joined: 03-October 11

Re: I need to create a count of probes in my binary search.

Posted 08 September 2012 - 09:07 PM

I can't believe I didn't see that. I am pretty sure I need a for loop for the probe. I changed the name and implemented it as a public int. I'm not sure what the proper count is. I think I need to handwrite the search out to figure the proper count. I changed it to the code below. I believe that's how I need to implement it or I should be close. It is now giving me the following output.

BINARY SEARCH RESULTS

Found California.
5 Probes

MS not found..
50 Probes

Found Texas.
5 Probes

Hwai not found..
50 Probes

Found California.
5 Probes

Found Indiana.
5 Probes

Okalahooma not found..
50 Probes

Found Florida.
3 Probes

Found Hawaii.
5 Probes

Alabam not found..
50 Probes

Found Alabama.
4 Probes

Puerto_Rico not found..
50 Probes

FL not found..
50 Probes

Found New_York.
4 Probes


I know it cannot have 50 probes if it's not found. Any idea why it is doing that or how to fix it?


private int binarySearch(String key) 
        {
           int lo = 0;
           int hi = numStates -1;
           int curIn;
           while(lo <= hi)
           {
               for (binProbe = 0;
                    binProbe < numStates;
                    binProbe++)
               {
                    curIn=lo+(hi - lo)/2;
                    if(myStates[curIn].getStateName().compareTo(key)>0)
                    {
                        hi=curIn-1;
                    }//end if(myStates[curIn].getStateName().compareTo(key)>0)
                    else if(myStates[curIn].getStateName().compareTo(key)<0)
                    {
                        lo=curIn+1;
                    }//end else if(myStates[curIn].getStateName().compareTo(key)<0)
                    else 
                    {
                        return curIn;
                    }//end else
               }//end for (binProbe = 0;binProbe < numStates;binProbe++)
           }//end while(lo <= hi)
           return -1;
        }//end binarySearch(String key)
}//end StateController()

Was This Post Helpful? 0
  • +
  • -

#6 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8332
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: I need to create a count of probes in my binary search.

Posted 08 September 2012 - 09:15 PM

Oufff... I would rather use a method that return both the number of probe and the index
You can use an array of int[] or a Point


private Point binarySearch(String key) 
        {
           int lo = 0;
           int hi = numStates -1;
           int curIn;
           int probe = 0;
           while(lo <= hi)
           {
               ++probe;

                    curIn=lo+(hi - lo)/2;
                    if(myStates[curIn].getStateName().compareTo(key)>0)
                    {
                        hi=curIn-1;
                    }//end if(myStates[curIn].getStateName().compareTo(key)>0)
                    else if(myStates[curIn].getStateName().compareTo(key)<0)
                    {
                        lo=curIn+1;
                    }//end else if(myStates[curIn].getStateName().compareTo(key)<0)
                    else 
                    {
                        return new Point(curIn, probe);
                    }//end else
           }//end while(lo <= hi)
           return new Point(-1, probe);
        }//end binarySearch(String key)
}//end StateController()


Was This Post Helpful? 1
  • +
  • -

#7 scy0846  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 68
  • Joined: 03-October 11

Re: I need to create a count of probes in my binary search.

Posted 08 September 2012 - 09:39 PM

I cannot seem to implement Point. It looks like I would have to create a class unless it's something I need to import, but I haven't found anything. I can't find any information on how an array of int[] would work. I don't have the binProbe returning because I have it as a public int and placed it in the code below.

public void binarySearch()
        {
            System.out.println("\n\n\n BINARY SEARCH RESULTS");
            for(int curIn=0; curIn<numKeys; curIn++)
            {
                String key = myKeys[curIn];
                int index =binarySearch(key);

                if(index!=-1)
                {
                    System.out.println(" \nFound "+key + ".\n" + (binProbe) + " Probes");
                }//end if(index!=-1)
                else
                {
                    System.out.println(" \n" + key + " not found." + ".\n" + binProbe + " Probes");
                }//end else
            }//end for(int curIn=0; curIn<numKeys; curIn++)
        }//end binarySearch()

    private Point binarySearch(String key) 
        {
           int lo = 0;
           int hi = numStates -1;
           int curIn;
           int probe = 0;
           while(lo <= hi)
           {
               ++probe;
               
                    curIn=lo+(hi - lo)/2;
                    if(myStates[curIn].getStateName().compareTo(key)>0)
                    {
                        hi=curIn-1;
                    }//end if(myStates[curIn].getStateName().compareTo(key)>0)
                    else if(myStates[curIn].getStateName().compareTo(key)<0)
                    {
                        lo=curIn+1;
                    }//end else if(myStates[curIn].getStateName().compareTo(key)<0)
                    else 
                    {
                        return new Point(curIn, probe);
                    }//end else
               
           }//end while(lo <= hi)
           return -1;
        }//end binarySearch(String key)
}//end StateController()

Was This Post Helpful? 0
  • +
  • -

#8 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8332
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: I need to create a count of probes in my binary search.

Posted 09 September 2012 - 10:44 AM

import java.awt.Point;
Was This Post Helpful? 1
  • +
  • -

#9 scy0846  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 68
  • Joined: 03-October 11

Re: I need to create a count of probes in my binary search.

Posted 09 September 2012 - 12:21 PM

I am getting an incomparable type where it says
if(index != -1)

I had to change index to a point because binarySearch(key) was changed to one in the process. Is there a way to somehow make it comparable. I tried (-1,binProbe) because from what I researched on Point is it places it into a coordinate I believe. I really want to understand this and I thank you for your help.

Point

public Point(int x,
int y)
Constructs and initializes a point at the specified (x, y) location in the coordinate space.
Parameters:
x - the x coordinate
y - the y coordinate


http://docs.oracle.c.../awt/Point.html



public void binarySearch()
        {
            System.out.println("\n\n\n BINARY SEARCH RESULTS");
            for(int curIn=0; curIn<numKeys; curIn++)
            {
                String key = myKeys[curIn];
                Point index =binarySearch(key);

                if(index != -1) //<---this is giving me the issue
                {
                    System.out.println(" \nFound "+key + ".\n" + (binProbe) + " Probes");
                }//end if(index!=-1)
                else
                {
                    System.out.println(" \n" + key + " not found." + ".\n" + binProbe + " Probes");
                }//end else
            }//end for(int curIn=0; curIn<numKeys; curIn++)
        }//end binarySearch()

    private Point binarySearch(String key) 
        {
           int lo = 0;
           int hi = numStates -1;
           int curIn;
           while(lo <= hi)
           {
               ++binProbe;
                curIn=lo+(hi - lo)/2;
                if(myStates[curIn].getStateName().compareTo(key)>0)
                {
                    hi=curIn-1;
                }//end if(myStates[curIn].getStateName().compareTo(key)>0)
                else if(myStates[curIn].getStateName().compareTo(key)<0)
                {
                    lo=curIn+1;
                }//end else if(myStates[curIn].getStateName().compareTo(key)<0)
                else 
                {
                    return new Point(curIn, binProbe);
                }//end else
           }//end while(lo <= hi)
           return new Point(-1,binProbe);
        }//end binarySearch(String key)
}//end StateController()

Was This Post Helpful? 0
  • +
  • -

#10 scy0846  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 68
  • Joined: 03-October 11

Re: I need to create a count of probes in my binary search.

Posted 09 September 2012 - 12:31 PM

Would I use a boolean for it?
Was This Post Helpful? 0
  • +
  • -

#11 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8332
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: I need to create a count of probes in my binary search.

Posted 09 September 2012 - 01:01 PM

You can access index.x and index.y
one being the index in the array, the other the number of probe
or you can

Point p = binarySearch(key);
int index = p.x;
int probe = p.y;
Was This Post Helpful? 0
  • +
  • -

#12 scy0846  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 68
  • Joined: 03-October 11

Re: I need to create a count of probes in my binary search.

Posted 09 September 2012 - 01:02 PM

nevermind boolean won't work because it's for objects.

I then tried
if(index.x != -1)//tried .y as well

that didn't work. With this I get the output...

BINARY SEARCH RESULTS

Found California.
6 Probes

Found MS.
11 Probes

Found Texas.
17 Probes

Found Hwai.
23 Probes

Found California.
29 Probes

Found Indiana.
35 Probes

Found Okalahooma.
41 Probes

Found Florida.
45 Probes

Found Hawaii.
51 Probes

Found Alabam.
56 Probes

Found Alabama.
61 Probes

Found Puerto_Rico.
66 Probes

Found FL.
72 Probes

Found New_York.
77 Probes

I know these are incorrect.
Was This Post Helpful? 0
  • +
  • -

#13 scy0846  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 68
  • Joined: 03-October 11

Re: I need to create a count of probes in my binary search.

Posted 09 September 2012 - 01:07 PM

Ah I had the same idea. Netbeans is helpful when you place a period after something incomparable. The problem is I am still getting 77 probes. The correct count should be 6 or less. 2^n
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1