Problem with Binary search method
here is the whole program
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.
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.
Re: Problem with Binary search method
Hi lenois,
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.
Re: Problem with Binary search method
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?
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.
