Results 1 to 5 of 5
Like Tree1Likes
  • 1 Post By Ronin

Thread: Problem with Binary search method

  1. #1
    lenois is offline Member
    Join Date
    Feb 2012
    Posts
    59
    Rep Power
    0

    Default Problem with Binary search method

    here is the whole program
    Java Code:
    import java.io.*;
    import javax.swing.JOptionPane;
    
    public class SortingSearching
    {
    	public static void main (String[]args)throws IOException
    	{
    		String[]fileNames=new String [2];
    		String[]inputData= new String[20];
    		String[]sortedList;
    		int ct;
    		
    		fileNames=getFileNames(fileNames);
    		ct=readFile(fileNames,inputData);
    		System.out.println(ct);
    		sortedList=sortFile(inputData,ct);
    		printToFile(sortedList,fileNames,ct);
    		searchList(sortedList,ct);
    				
    				
    		
    	}
    	/************************************************************************
    	*Function getFileNames ||this function gets user inputed filenames and	*
    	*stores them in a string array for later use.									*
    	*Pre:fileNames array Post:returns the array with the filenames				*
    	*************************************************************************/
    	public static String[] getFileNames(String[]fileNames)
    	{
    		fileNames[0]=JOptionPane.showInputDialog("Please enter name of input File:");
    		fileNames[1]=JOptionPane.showInputDialog("Please enter name of output File:");
    		
    		return fileNames;
    	}
    	/***************************************************************************
    	*Function readFile ||This function reads the text in the user chosen		 	*
    	*file and stores up to 20 in a string array.											*
    	*Pre:fileNames, inputData arrays Post:returns up to 20 strings in inputData*
    	****************************************************************************/
    	public static int readFile(String[]fileNames,
    											  String[]inputData)throws IOException
    	{
    		int i=0;
    		boolean test=false;
    		String holder;
    		
    		BufferedReader inFile = 
                         new BufferedReader( new FileReader(fileNames[0]+".txt"));
    		
    		while(test!=true)
    		{
    			holder=inFile.readLine();
    			if (holder==null)
    			{
    				test=true;
    			}else if(i==20)
    			{
    			 	test=true;
    			}else
    			{
    				inputData[i]=holder;
    				i++;
    			}
    			
    		}
    		inFile.close();	
    		
    		return i;
    	}
    	
    	/************************************************************************
    	*Function sortFile ||this function sorts the data aquired by readFile	*
    	*and uses an improved bubble sort to sort them									*
    	*Pre:inputData Array Post:returns a sorted array with the filenames				*
    	*************************************************************************/
    	public static String[] sortFile(String[] inputData,
    											  int ct)
    	{
    		int lastPos;
    		int index;
    		String temp;
    		
    		
    		for(lastPos=ct; lastPos>=0; lastPos--)
    		{
    			for(index=0;index<ct;index++)
    			{
    				if(inputData[index+1]!=null&&index<ct)
    				{					
    					if(inputData[index].compareTo(inputData[index+1])>0)
    					{
    						temp=inputData[index];
    						inputData[index]=inputData[index+1];
    						inputData[index+1]=temp;
    					
    					}
    				}
    			}
    		}
    	return inputData;
    	}
    	/************************************************************************
    	*Function printToFile ||this function prints the sorted array to a file	*
    	*																								*
    	*Pre:SortedList array Post:none														*
    	*************************************************************************/
    	public static void printToFile(String[] sortedList,
    											 String[] fileNames,
    											 int ct)throws IOException
    	{
    		PrintWriter outFile=
    						new PrintWriter(fileNames[1]+".txt");
    		int index=0;
    		
    		for(index=0;index<ct;index++)
    		{
    			
    			outFile.println(index+"  "+sortedList[index]);//prints the sorted array to a file
    			
    		}
    		outFile.close();
    	}
    	/************************************************************************
    	*Function searchList ||function Searches list for user inputted word		*
    	*																								*
    	*Pre:SortedList array Post:none														*
    	*************************************************************************/
    	public static void searchList(String[] sortedList,
    											int ct)
    	{
    		String input;
    		input=JOptionPane.showInputDialog("Please enter a word to search for, or stop to stop");
    		
    		
    		
    		while(!input.equalsIgnoreCase("stop"))
    		{
    			
    			int first=0;
    			int last=ct-1;
    			int position=-1;
    			boolean found=false;
    			int middle;
    			
    			
    			System.out.println(last);
    			
    			
    			middle=(first=last)/2;
    			
    			while(!found&&first<last)
    			{       middle=(first+last)/2;
    				if(sortedList[middle].equalsIgnoreCase(input))
    				{
    					found=true;
    					position=middle; 
    				}else if(sortedList[middle].compareTo(input)>0)
    				{
    					first=middle+1;
    				}else
    				{
    					last=middle-1;
    				}
    			}
    			JOptionPane.showMessageDialog(null,input+" found at position "+position); 
    			input=JOptionPane.showInputDialog("Please enter a word to search for, or stop to stop");	
    		}
    	}
    }
    The last Method is the one that is not working. It is a simple binary search, but no matter whether the input is there or not, it returns -1. No errors are reported.
    Last edited by lenois; 02-08-2013 at 12:19 AM.

  2. #2
    lenois is offline Member
    Join Date
    Feb 2012
    Posts
    59
    Rep Power
    0

    Default Re: Problem with Binary search method

    Never mind I fixed it, i had a simple typo.

    but any comment on the code itself would be useful. Whether it is readable, are there too many loops, and other ways to improve it.

  3. #3
    Ronin is offline Senior Member
    Join Date
    Oct 2010
    Posts
    335
    Rep Power
    4

    Default Re: Problem with Binary search method

    Hi lenois,
    Java Code:
    if(inputData[index+1]!=null&&index<ct)
    The above comment is enclosed in a for loop which already checks if index is smaller than ct. The last part of the above code on line 88 is redundant.

    Regards.
    lenois likes this.

  4. #4
    lenois is offline Member
    Join Date
    Feb 2012
    Posts
    59
    Rep Power
    0

    Default Re: Problem with Binary search method

    Java Code:
    import java.io.*;
    import javax.swing.JOptionPane;
    
    public class SortingSearching
    {
    	public static void main (String[]args)throws IOException
    	{
    		String[]fileNames=new String [2];
    		String[]inputData= new String[20];
    		String[]sortedList;
    		int ct;
    		
    		fileNames=getFileNames(fileNames);
    		ct=readFile(fileNames,inputData);
    		sortedList=sortFile(inputData,ct);
    		printToFile(sortedList,fileNames,ct);
    		searchList(sortedList,ct);
    				
    				
    		
    	}
    	/************************************************************************
    	*Function getFileNames ||this function gets user inputed filenames and	*
    	*stores them in a string array for later use.									*
    	*Pre:fileNames array Post:returns the array with the filenames				*
    	*************************************************************************/
    	public static String[] getFileNames(String[]fileNames)
    	{
    		fileNames[0]=JOptionPane.showInputDialog("Please enter name of input File:");
    		fileNames[1]=JOptionPane.showInputDialog("Please enter name of output File:");
    		
    		return fileNames;
    	}
    	/***************************************************************************
    	*Function readFile ||This function reads the text in the user chosen		 	*
    	*file and stores up to 20 in a string array.											*
    	*Pre:fileNames, inputData arrays Post:returns up to 20 strings in inputData*
    	****************************************************************************/
    	public static int readFile(String[]fileNames,
    											  String[]inputData)throws IOException
    	{
    		int i=0;
    		boolean test=false;
    		String holder;
    		
    		BufferedReader inFile = 
                         new BufferedReader( new FileReader(fileNames[0]+".txt"));
    		
    		while(test!=true)
    		{
    			holder=inFile.readLine();
    			if (holder==null)
    			{
    				test=true;
    			}else if(i==20)
    			{
    			 	test=true;
    			}else
    			{
    				inputData[i]=holder;
    				i++;
    			}
    			
    		}
    		inFile.close();	
    		
    		return i;
    	}
    	
    	/************************************************************************
    	*Function sortFile ||this function sorts the data aquired by readFile	*
    	*and uses an improved bubble sort to sort them									*
    	*Pre:inputData Array Post:returns a sorted array with the filenames				*
    	*************************************************************************/
    	public static String[] sortFile(String[] inputData,
    											  int ct)
    	{
    		int lastPos;
    		int index;
    		String temp;
    		
    		
    		for(lastPos=ct; lastPos>=0; lastPos--)
    		{
    			for(index=0;index<ct;index++)
    			{
    								
    				if(index+1!=20&&inputData[index+1]!=null&&inputData[index].compareTo(inputData[index+1])>0)
    				{
    					temp=inputData[index];
    					inputData[index]=inputData[index+1];
    					inputData[index+1]=temp;
    					
    				}
    				
    			}
    		}
    	return inputData;
    	}
    	/************************************************************************
    	*Function printToFile ||this function prints the sorted array to a file	*
    	*																								*
    	*Pre:SortedList array Post:none														*
    	*************************************************************************/
    	public static void printToFile(String[] sortedList,
    											 String[] fileNames,
    											 int ct)throws IOException
    	{
    		PrintWriter outFile=
    						new PrintWriter(fileNames[1]+".txt");
    		int index=0;
    		
    		for(index=0;index<ct;index++)
    		{
    			
    			outFile.println(index+"  "+sortedList[index]);//prints the sorted array to a file
    			
    		}
    		outFile.close();
    	}
    	/************************************************************************
    	*Function searchList ||function Searches list for user inputted word		*
    	*																								*
    	*Pre:SortedList array Post:none														*
    	*************************************************************************/
    	public static void searchList(String[] sortedList,
    											int ct)
    	{
    		String input;
    		input=JOptionPane.showInputDialog("Please enter a word to search for, or stop to stop");
    		
    		
    		
    		while(!input.equalsIgnoreCase("stop"))
    		{
    			
    			int first=0;
    			int last=ct;
    			int position=-1;
    			boolean found=false;
    			int middle;
    			
    			
    			middle=(first+last)/2;
    			
    			while(!found&&first<last)
    			{
    				middle=(first+last)/2;
    				if(sortedList[middle].equalsIgnoreCase(input))
    				{
    					found=true;
    					position=middle; 
    				}else if(sortedList[middle].compareToIgnoreCase(input)>0)
    				{
    					last=middle-1;
    				}else
    				{
    					first=middle+1;
    				}
    			}
    			JOptionPane.showMessageDialog(null,input+" found at position "+position); 
    			input=JOptionPane.showInputDialog("Please enter a word to search for, or stop to stop");	
    		}
    	}
    }
    here is my code as it stands now, I was doing some final test and noticed that it can't seem to find object in position 0 every other array location works fine, but if I look for the string in 0 it returns -1 which means not found, any ideas?

  5. #5
    lenois is offline Member
    Join Date
    Feb 2012
    Posts
    59
    Rep Power
    0

    Default Re: Problem with Binary search method

    tested middle, and the problem seems to be that middle never gets below 1
    nevermind, it works if i set last to middle, although I imagine there is a better way to do it.
    Last edited by lenois; 02-14-2013 at 03:40 PM.

Similar Threads

  1. Binary Search Method
    By 8xjesterx8 in forum New To Java
    Replies: 0
    Last Post: 04-09-2011, 01:33 AM
  2. Binary search problem
    By billy in forum New To Java
    Replies: 3
    Last Post: 10-08-2010, 08:43 PM
  3. implement binary search method using recursion?
    By chopo1980 in forum New To Java
    Replies: 1
    Last Post: 12-12-2009, 03:58 PM
  4. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 01:42 AM
  5. Replies: 5
    Last Post: 10-13-2009, 01:35 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •