I need help with this 2 questions...Merge Sort and Binary Search... Please expla
ID: 3545471 • Letter: I
Question
I need help with this 2 questions...Merge Sort and Binary Search...
Please explain each question in details and every step for how to do it...
Thank you.
Merge Sort:
Binary Search:
NOTE: the end position is one past the last element of the array to be sorted. Private void mergeSort (int[ [ a, int start, int end) { if (start lt end - 1) { int mid = (start + end) / 2; mergeSort (a, start, mid); mergeSort (a, mid, end); merge (a, start, mid, end); } } private void merge (int [ ] a, int start, int mid, int end) { //code is not shown here } On the next page is the recursive call tree diagram for the above mergesort ( ) method where the array, a, is defined as follows: int [ ] a = { 5, 4, 21, 2, 7}; and the call: mergeSort (a, 0, 5); is made to the mergeSort ( ) method given above. In the diagram on the next page, each recursive call is labelled, A, B, C, etc. In the boxes below show the elements of the array, a, after the recursive call marked A in the diagram has finished executing. private int binarySearch (int [ ] array, int first, int last, int value) { int index; if (first gt= last) { return -1; } int mid = (first + last) / 2; if (value == array[mid]) { //*** return mid; } if (value lt array [mid]) { index = binarySerach (array, mid + 1, last, value); } return index; } The following array of numbers (the indexes are shown in a smaller font above each number) is being searched for the value 23 using the above binarySearch ( ) method: int result = binarySearch (array, 0, 12, 23); Show all the elements which are compared to 23 as the code is executed, i.e., write the element values (not the index of the elements) which are compared at the position marked *** in the code above.Explanation / Answer
Binary Search :
The following numbers will be compared with 23 :
69, 54, 21, 23
First call has start =0 and end = 12, so mid = 6. So 23 is compared with the value at 6th index which is 69. Since 23 is less than 63, so end becomes 6 start remains 0 and in the second iteration, mid becomes 3.
So, in second iteration 23 is compared with element at 3rd index which is 54. Since 23 is less than 54, so end becomes 3 start remains 0 and in the third iteration, mid becomes 1.
So, in third iteration 23 is compared with element at 1st index which is 21. Since 23 is greater than 21, so end remains 3 start becomes 1 and in the third iteration, mid becomes 2.
So, in 4th iteration 23 is compared with element at 2nd index which is 23. Since 23 is equal to 23, the element is found and the index 2 is returned.
Please explain what you want for the first part?