Let tree T be this tree List the order of the nodes visited by depth_first_searc

Question

Let tree T be this tree List the order of the nodes visited by depth_first_search(T, 'F'): List the order of the nodes visited by bfs_queue(T, 'F'): Given an array containing the sequence 1, 5, 29, 45, 67, 76, 92, 104, 187, 234 (in that order) state each comparison made in finding the number 234 using linear search. (For example, 234: 1 is a comparison of 234 with 1.) state each comparison made in determining that the number 48 is not present using linear search. Given an array containing the sequence 1, 5, 29, 45, 67, 76, 92, 104, 187, 234 (in that order) state each comparison made in finding the number 234 using binary search. (For example, 234: 1 is a comparison of 234 with 1.) state each comparison made in determining that the number 48 is not present using binary search.

Explanation / Answer

print(binarySearch(testlist, 13))

It is possible to take greater advantage of the ordered list if we are clever with our comparisons. In the sequential search, when we compare against the first item, there are at most n1

more items to look through if the first item is not what we are looking for. Instead of searching the list in sequence, a binary search will start by examining the middle item. If that item is the one we are searching for, we are done. If it is not the correct item, we can use the ordered nature of the list to eliminate half of the remaining items. If the item we are searching for is greater than the middle item, we know that the entire lower half of the list as well as the middle item can be eliminated from further consideration. The item, if it is in the list, must be in the upper half.

We can then repeat the process with the upper half. Start at the middle item and compare it against what we are looking for. Again, we either find it or split the list in half, therefore eliminating another large part of our possible search space

def binarySearch(alist, item): 2     first = 0 3     last = len(alist)-1 4     found = False 5 6     while first<=last and not found: 7         midpoint = (first + last)//2 8         if alist[midpoint] == item: 9             found = True 10         else: 11             if item < alist[midpoint]: 12                 last = midpoint-1 13             else: 14                 first = midpoint+1 15 16     return found 17 18 testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,] 19 print(binarySearch(testlist, 3)) 20

print(binarySearch(testlist, 13))

It is possible to take greater advantage of the ordered list if we are clever with our comparisons. In the sequential search, when we compare against the first item, there are at most n1

more items to look through if the first item is not what we are looking for. Instead of searching the list in sequence, a binary search will start by examining the middle item. If that item is the one we are searching for, we are done. If it is not the correct item, we can use the ordered nature of the list to eliminate half of the remaining items. If the item we are searching for is greater than the middle item, we know that the entire lower half of the list as well as the middle item can be eliminated from further consideration. The item, if it is in the list, must be in the upper half.

We can then repeat the process with the upper half. Start at the middle item and compare it against what we are looking for. Again, we either find it or split the list in half, therefore eliminating another large part of our possible search space

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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