Q. Need to write a program to take a input file(input.txt) compare it with the d

ID: 3586969 • Letter: Q

Question

Q. Need to write a program to take a input file(input.txt) compare it with the dictionary file and output the words misspelled with their corresponding occurence in a output.txt file. also need to have a time complexity table for binary search and sort that contains: n #operations T(n) O(f(n)).

Requirements:

-need to search clean sorted dictionary only with

-sort the dictionary with one slow and and one fast algorithm

-need to use recursive algorithm for searching and sorting words in the file to be compared

-need to use binary search to find out if a word is misspelt.

-output.txt file should contain all the letters in lowercase

in short( need one effiecient and one ineffiecient sorting; need to use efficient search(binary search); recursion required, analyze O())

Explanation / Answer

import java.io.*;

public class MyRecursiveBinary {

public static int recursiveBinary(int[] sortedArray, int start, int end, int key) {

if (start < end) {

int mid = start + (end - start) / 2;

if (key < sortedArray[mid]) {

return recursiveBinary(sortedArray, start, mid, key);

} else if (key > sortedArray[mid]) {

return recursiveBinary(sortedArray, mid+1, end , key);

} else {

return mid;

}

return -(start + 1);

}

public static void main(String[] args) {

int[] arr1 = {2,45,234,567,876,900,976,999};

int index = recursiveBinary(arr1,0,arr1.length,45);

System.out.println("Found 45 at "+index+" index");

index = recursiveBinarySearch(arr1,0,arr1.length,999);

System.out.println("Found 999 at "+index+" index");

index = recursiveBinarySearch(arr1,0,arr1.length,876);

System.out.println("Found 876 at "+index+" index");

}