Trace six searches by hand on the following datasets. Unsorted Data Set: 5, 2, 1

Question

Trace six searches by hand on the following datasets.

Unsorted Data Set: 5, 2, 12, 7, 3, 9, 8, 6

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

To trace a linear/sequential search, list each array index that is visited.

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

Q1.

Trace the unsorted data set using a linear (sequential) search.

Unsorted Data Set: 5, 2, 12, 7, 3, 9, 8, 6

Search target: 3

To trace a linear search, list each array index that is visited.

Q2.

Trace the unsorted data set using a linear/sequential search.

Unsorted Data Set: 5, 2, 12, 7, 3, 9, 8, 6

Search target: 4

To trace a linear search, list each array index that is visited.

Q3.

Trace the sorted data set using a linear/sequential search (optimized for sorted data).

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

Search target: 18

To trace a linear search, list each array index that is visited.

Explanation / Answer

Q1.

Trace the unsorted data set using a linear (sequential) search.

Unsorted Data Set: 5, 2, 12, 7, 3, 9, 8, 6

Search target: 3

<Linear Search/Sequential Search> : We need to search 3 , It will start froim index 0 , 3 is not equal to 5
-> Move forward to next element , 2!=3 , move forward 12!=3 , move forward 7!=3 ..Move forward
Now 3 is equal to 3..return the index of element i.e 4

<Binary Search> : Cannot apply to unsorted data..Results are random can/cannot be found.

Q2.

Trace the unsorted data set using a linear/sequential search.

Unsorted Data Set: 5, 2, 12, 7, 3, 9, 8, 6

Search target: 4

To trace a linear search, list each array index that is visited.

<Linear Search/Sequential Search> : We need to search 4 , It will start froim index 0 , 4 is not equal to 5
-> Move forward to next element , 2!=4 , move forward 12!=4 , move forward 7!=4 ..Move forward 3!=4
Move forward 9!=4, Move forward 8!=4 , Move forward 6!=4 . We reached till the end of data an delement is not found, return -1

<Binary Search> : Cannot apply to unsorted data..Results are random can/cannot be found.

Q3.

Trace the sorted data set using a linear/sequential search (optimized for sorted data).

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

Search target: 18

To trace a linear search, list each array index that is visited.

<Linear Search/Sequential Search> : We need to search 18 , It will start froim index 0 , 18 is not equal to 3
-> Move forward to next element , 5!=18 , move forward 8!=18 , move forward 9!=18 ..Move forward 12!=18
Move forward 14!=18, Move forward 18==18 , return the index of element i.e 6

<Binary Search> : low = 0 , high = 11 . [Index of array]
mid = 5

value at mid = 14 so 14 != 18
we see that mid = 14 and 18 > 14 means element is in 2nd half
so , low = mid +1 = 1
high remains at = 11
Now mid =  (1+11)/2 = 6
value at index 6 is 18==18 , means found element at index 6

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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