Question

#2Trace These JAVA searches by hand on the following dataset.

Sorted Data Set: 3, 5, 8, 9, 12, 14, 18, 19, 21, 23, 24, 26

#Trace the sorted data set using a binary search.

Search target: 23

#Trace the sorted data set using a binary search.

Search target: 15

(To trace a binary search, list the value of first, last, and mid for each pass through the method.)

Use this method:

private static <T extends Comparable<? super T>>
   boolean binarySearch(T[] anArray, int first, int last, T desiredItem)
{
   boolean found;
   int mid=first+(last-first)/2;
  
   if (first>last)
       found = false;
   else if (desiredItem.equals(anArray[mid]))
       found true;
   else if (desiredItem.compareTo(anArray[mid])<0)
       found = binarySearch(anArray, first, mid-1, desiredItem);
   else
       found = binarySearch(anArray, mid +1, last, desiredItem);
   return
       found;
}

Answer 1

Sorted data set given as follows:

3          5          8          9          12        14        18        19        21        23        24        26

1. To trace the data set using binary search method given with search target= 23 the passes and iterations are as follows:

Iteration	1	2	3	4
First	1	7	10	10
Last	12	12	12	11
Mid	6	9	11	10
Array[mid]	14	21	24	23
desiredItem.compareto(Array[mid])	23>14	23>21	23<24	23=23
index	6	9	11	10

So, the number 23 is found on the index number 10 and in 4^th iteration

.

1. To trace the data set using binary search method given with search target =15 the passes and iterations are as follows:

Iteration	1	2	3	4	5	6	7	8
First	1	7	7	7	7	7	7	7
Last	12	12	11	10	9	8	7	6
Mid	6	9	9	8	8	7	7	6
Array[mid]	14	21	21	19	19	18	18	14
desiredItem.compareto(Array[mid])	15>14	15<21	15<21	15<19	15<19	15<18	15<18	15>14
Index	6	9	9	8	8	7	7	6

So, we found that the number 15 is not present in a given sorted list. But, if we want to place the number 15, then it can be placed in between index number 6 and 7.