Directions: Trace six searches by hand on the following datasets. Unsorted Data

Question

Directions: 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.

For the linear/sequential search, use the "optimized" versions.

This means you will end the search when the target is found.

For sorted lists, you will also end the search once you know the target cannot be found.

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

Show work:

Trace 1: | unsorted data | linear /sequential | Target 3.

Trace 2: | unsorted data | linear /sequential | Target 4.

Trace 3: | sorted data | linear /sequential | Target 18.

Trace 4: | sorted data | linear /sequential | Target 15.

Trace 5: | sorted data | Binary | Target 23.

Trace 6: | sorted data | Binary | Target 15.

Explanation / Answer

Please find my answer for first 3 traversal.

Question is big so please repost other parts in separate post.

Trace 1: | unsorted data | linear /sequential | Target 3.

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.

= > Trace 2: | unsorted data | linear /sequential | Target 4.

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.

= > Trace 3: | sorted data | linear /sequential | Target 18.

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 D
• Subjects

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