How to modify the following code to satisfy the conditions: 1. The length of the
ID: 3912868 • Letter: H
Question
How to modify the following code to satisfy the conditions:
1. The length of the shorter array is the square root of the length of the longer array
2.To add an element, use insertion sort to insert the element into the shorter array. If the short
array fills up, re-allocate the shorter and longer arrays and merge the two old arrays into the
new longer array. The new short array is empty.
3. To search an element, use binary search on both the long and the short arrays.
4. Search time is O(lg n) time complexity
———————————————————————————————————————————————————————————————————————————————————
import java.util.Arrays;
public class Problem1Implementation
{
int count = 0;
int longerArray[];
int shorterArray[];
public Problem1Implementation()
{
shorterArray = new int[1];
longerArray = new int[0];
}
public void mergeArrays(int array1[], int array2[], int array1Length, int array2Length, int arr3[])
{
int a = 0, b = 0, c = 0;
while (a < array1Length && b < array2Length)
{
if (array1[a] < array2[b])
{
arr3[c++] = array1[a++];
}
else
{
arr3[c++] = array2[b++];
}
}
while (a < array1Length)
arr3[c++] = array1[a++];
while (b < array2Length)
arr3[c++] = array2[b++];
}
public void reallocate()
{
System.out.println("Relocation happening.");
int newBiggerArray[] = new int[longerArray.length + shorterArray.length];
mergeArrays(longerArray, shorterArray, longerArray.length, shorterArray.length, newBiggerArray);
// the length of the shorter array is the square root of the length of the longer array
shorterArray = new int[(int) Math.sqrt(newBiggerArray.length)];
longerArray = newBiggerArray;
count = 0;
}
public void add(int e)
{
if (count == shorterArray.length)
{
reallocate();
}
int i = count - 1;
while (i >= 0 && e < shorterArray[i])
{
shorterArray[i + 1] = shorterArray[i];
i--;
}
shorterArray[i + 1] = e;
count++;
}
public void search(int e)
{
int index = Arrays.binarySearch(longerArray, e);
if (index >= 0)
{
System.out.println("Element " + e + " found in bigger array at index: " + index);
return;
}
index = Arrays.binarySearch(shorterArray, 0, count, e);
if (index >= 0)
{
System.out.println("Element " + e + " found in smaller array at index: " + index);
return;
}
System.out.println("Element " + e + " not found");
return;
}
public void printArrays()
{
System.out.println("Longer Array: " + Arrays.toString(longerArray));
System.out.println("Shorter Array: " + Arrays.toString(shorterArray) + " ");
}
public static void main(String[] args)
{
Problem1Implementation se = new Problem1Implementation();
se.printArrays();
System.out.println("Adding 5");
se.add(5);
se.printArrays();
System.out.println("Adding 15");
se.add(15);
se.printArrays();
System.out.println("Adding 11");
se.add(11);
se.printArrays();
System.out.println("Adding 41");
se.add(41);
se.printArrays();
System.out.println("Adding 31");
se.add(31);
se.printArrays();
System.out.println("Adding 31");
se.add(31);
se.printArrays();
System.out.println("Adding 27");
se.add(27);
se.printArrays();
System.out.println("Adding 4");
se.add(4);
se.printArrays();
System.out.println("Searching for 15:");
se.search(15);
System.out.println("Searching for 4:");
se.search(4);
System.out.println("Searching for 23:");
se.search(23);
}
}
Explanation / Answer
Sol: From what I can understand from the question, this should work.
import java.util.Arrays;
public class Problem1Implementation
{
int count = 0;
int longerArray[];
int shorterArray[];
public Problem1Implementation()
{
shorterArray = new int[1];
longerArray = new int[0];
}
public void mergeArrays(int array1[], int array2[], int array1Length, int array2Length, int arr3[])
{
int a = 0, b = 0, c = 0;
while (a < array1Length && b < array2Length)
{
if (array1[a] < array2[b])
{
arr3[c++] = array1[a++];
}
else
{
arr3[c++] = array2[b++];
}
}
while (a < array1Length)
arr3[c++] = array1[a++];
while (b < array2Length)
arr3[c++] = array2[b++];
}
public void reallocate()
{
System.out.println("Relocation happening.");
int newBiggerArray[] = new int[longerArray.length + shorterArray.length];
mergeArrays(longerArray, shorterArray, longerArray.length, shorterArray.length, newBiggerArray);
// the length of the shorter array is the square root of the length of the longer array
shorterArray = new int[(int) Math.sqrt(newBiggerArray.length)];
longerArray = newBiggerArray;
count = 0;
}
public void add(int e)
{
if (count == shorterArray.length)
{
reallocate();
}
int i = count - 1;
while (i >= 0 && e < shorterArray[i])
{
shorterArray[i + 1] = shorterArray[i];
i--;
}
shorterArray[i + 1] = e;
count++;
}
public void search(int e)
{
int index = Arrays.binarySearch(longerArray, e);
if (index >= 0)
{
System.out.println("Element " + e + " found in bigger array at index: " + index);
return;
}
index = Arrays.binarySearch(shorterArray, 0, count, e);
if (index >= 0)
{
System.out.println("Element " + e + " found in smaller array at index: " + index);
return;
}
System.out.println("Element " + e + " not found");
return;
}
public void printArrays()
{
System.out.println("Longer Array: " + Arrays.toString(longerArray));
System.out.println("Shorter Array: " + Arrays.toString(shorterArray) + " ");
}
public static void main(String[] args)
{
Problem1Implementation se = new Problem1Implementation();
se.printArrays();
System.out.println("Adding 5");
se.add(5);
se.printArrays();
System.out.println("Adding 15");
se.add(15);
se.printArrays();
System.out.println("Adding 11");
se.add(11);
se.printArrays();
System.out.println("Adding 41");
se.add(41);
se.printArrays();
System.out.println("Adding 31");
se.add(31);
se.printArrays();
System.out.println("Adding 31");
se.add(31);
se.printArrays();
System.out.println("Adding 27");
se.add(27);
se.printArrays();
System.out.println("Adding 4");
se.add(4);
se.printArrays();
System.out.println("Searching for 15:");
se.search(15);
System.out.println("Searching for 4:");
se.search(4);
System.out.println("Searching for 23:");
se.search(23);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.