Question: 1. Consider a search algorithm that compares an item with an element one-third of the way through the list; based on that comparison, it then searches either the first one-third or the second two-thirds of the list.
2. Draw the decision tree for searching a nine-element sorted list. What is the depth of the tree? Does it appear that this is an optimal algorithm in the worst case?
2. Draw the decision tree for sequential search on a list of six elements.