Write a Java program to implement one of the following two functions, boolean Fi

Question

Write a Java program to implement one of the following two functions, boolean Find_Number(int[] arr, int num) or boolean Find_Number(ArrayList arr, int num) The two functions take either an integer array or an integer ArrayList and an integer num as input. The function should return true if num appeasers in arr for at least once. Return false if otherwise. Implement the function by yourself and do not use any system-provided array-element searching function, such as ArrayList.contains. Requirements: 1) Use the merge sort function you implemented in the previous problem to sort the input array or ArrayList first. 2) Then try to find if num appeasers in arr. 3) No point will be given if you go through all the integers in arr one by one to find num. Instead, take advantage of the fact that arr is sorted. Hint: You should be able to decide if num appeasers in arr by checking at most log n positions in arr where n is the length of arr. What to program: The skeleton of the program is also included in MergeSort.java. Finish the program by yourself. What to submit: Submit just one copy of MergeSort.java that contains finished program of both problem 1 and 2. Function needs to be implimented by yourself, not calling for a system method. Thanks.

Explanation / Answer

public class MergeSort {
  
   // all auxiliary
   private static int[] array;
private static int[] tempMergArr;
private static int length;
  
// merge sort
   public static void merge_sort(int inputArr[]) {
   array = inputArr;
   length = inputArr.length; // input aray
   tempMergArr = new int[length];// temp array
   doMergeSort(0, length - 1);
   }
     
   private static void doMergeSort(int lowerIndex, int higherIndex) {
     
   if (lowerIndex < higherIndex) {
   int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
   // Below step sorts the left side of the array
   doMergeSort(lowerIndex, middle);
   // Below step sorts the right side of the array
   doMergeSort(middle + 1, higherIndex);
   // Now merge both sides
   mergeParts(lowerIndex, middle, higherIndex);
   }
   }
     
   private static void mergeParts(int lowerIndex, int middle, int higherIndex) {
     
   for (int i = lowerIndex; i <= higherIndex; i++) {
   tempMergArr[i] = array[i];
   }
   int i = lowerIndex;
   int j = middle + 1;
   int k = lowerIndex;
   while (i <= middle && j <= higherIndex) {
   if (tempMergArr[i] <= tempMergArr[j]) {
   array[k] = tempMergArr[i];
   i++;
   } else {
   array[k] = tempMergArr[j];
   j++;
   }
   k++;
   }
   while (i <= middle) {
   array[k] = tempMergArr[i];
   k++;
   i++;
   }
     
   }
  
   //find method
static boolean Find_Number(int[] arr, int num){
  
   int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (num == arr[mid]) {
return true;
}
if (num < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
  
public static void main(String[] args) {
// You can test your implemented functions here.
   int arr[] = new int[] {1,7,5,9,3,5,2};
merge_sort(arr);
for(int i : arr)
   System.out.println(i+" ");
System.out.println("Fing 4 ? "+ Find_Number(arr, 4));

}

}

/*

Output:

1
2
3
5
5
7
9
Fing 4 ? false

*/

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.