$12\mathrm{.}8\mathrm{.}3$: Worst and best case running time for binary search.

help$\_$outline

$($a$)$

Consider running binary search on input list:

$(2,5,8,11,15,18,23,29,31,35)$

In searching for a target item x that is in the list, the running time of the algorithm may differ depending on which item from the list is the target. Give a target item x$,$ selected from the list, that results in the best running time. Given a target item, selected from the list, that results in the worst running time.

$($b$)$

For some input lists, the time to search for an item in the list under binary search is the same for all items in the list. Characterize the input lists that have this property. Assume the items in the list are all different.