Question

I'm trying to make a recursive binary search that checks whether or not the words in a file are correct by comparing it to a dictionary file, but for some reason the method I'm using below is not working and is outputting all the words in the file I am checking as incorrect. (the dictionary is organized in alphabetical order however the file "oliver.txt" is not)

my question is what do I have to do to make this work?

public static int binarySpellcheck(String []dictionary,String [] file,int low,int high,int index){

int mid = (low+high)/2;
int key = chartoInt(file[i]);/*converts the string to its numerical value
equivalent */

if (low>high){
System.out.println("Couldn't find this word chief: "+file[i]);

incorrectWords++;
return -1;//not on the list
}//if
  
if(chartoInt(dictionary[mid])== key){
System.out.println("We found this word chief"+(dictionary[mid]));
correctWords++;
return mid;
}else if(chartoInt(dictionary[mid]) > key){
  
return binarySpellcheck(dictionary,file,low,mid-1,i);
  
}else
  
return binarySpellcheck(dictionary,file,mid+1,high,i);
  
}//binarySpellcheck

public static int chartoInt(String x){//returns the numerical sum of a word (ASCII)
String[]wordArray= new String [x.toCharArray().length];
int wordSum=0;
for (int i = 0; i < wordArray.length; i++) {
wordSum+=(int)x.toCharArray()[i];

}
return wordSum;
}

incorrectWords and correctWords are defined early in the program as global variables

the programming language is java

Answer 1

1.CODE->

public class BinarySearchString {
  
   public static int incorrectWords=0;
   public static int correctWords=0;
  
  
   public static int binarySpellcheck(String[] dictionary,String[] file, int low, int high ,int index)
   {
       if(low>high) //base case to terminate recursion
       {
           incorrectWords++;
           System.out.println("Couldn't find this word chief : "+file[index]);
           return -1;
       }
      
       int mid = (low+high)/2; //middle index
      
       int res = file[index].compareTo(dictionary[mid]); // compareTo method returns either a positive or negative number or zero depending on the 2 strings
      
       if(res==0) // res==0 indicates both strings are same or equal
       {
           correctWords++;
           System.out.println("We found this word chief : "+(dictionary[mid]));
           return mid;
       }
      
       else if(res>0) //res>0 indicates that string dicitionary[mid] lexicographically less than the string file[index].
       return binarySpellcheck(dictionary,file,mid+1,high,index);
      
       else
           return binarySpellcheck(dictionary,file,low,mid-1,index); //res<0 indicates that string dicitionary[mid] lexicographically greater than the string file[index].
          
      
   }
  
     
  
   public static void main(String[] args)
   {
       String dictionary[]= {"apple","ball","cat","dog","eye"};
       String file[]= {"ant","bat","cat"};
      
       for(int i=0;i<file.length;i++)
           binarySpellcheck(dictionary,file,0,dictionary.length-1,i);
      
       System.out.println("Number of correct words : "+correctWords);
       System.out.println("Number of incorrect words : "+incorrectWords);
   }

}

2.OUTPUT->

WORKING OF COMPARE TO METHOD()->

The value 0 if the argument is a string lexicographically equal to this string. a value less than 0 if the argument is a string lexicographically greater than this string. and a value greater than 0 if the argument is a string lexicographically less than this string.

PROBLEM WITH YOUR CODE ->

previously you are using a function which is giving you the sum of ASCII values of the characters of a string.

this can lead to problem , when 2 strings have sum it will always show positive result.

Consider this scenario ->

Dictionary array contains "ant" but not contains "eye"

sum= a+n+t= 97+110+116=323

sum= e+y+e=101+121+101=323

The file contains "eye" and when we search that dictionary contains "eye" , it may show the positive result due to the presence of "ant" whose sum is same as "eye".

Second thing the dictionary is sorted lexographically , it does not mean that if you find character sum of all the strings then they will also be in incrasing order

For example -> ant , be are in dictionary order but sum are not in increasing order

sum for ant=323

sum for be=98+101=199

clearly they are not in sorted order and binary search can be only used for sorted data

so it is better to use compareTo method than this method , because using this method will give you ambigious results.

I HOPE YOU WILL GET IT.............YOUR RESPONSE WILL BE HIGHLY APPRECIATED