(3) CSC 211: binary search and selection sort

In which situations is worst-case analysis preferable to the other two analysis methods?

worst case analysis is preferable, in real time systems because immidiate response is crucial like in emergency response applications. we want to know the maximum time an operation could take regaudless of the input.

In which situations is average-case analysis preferable to the other two analysis methods?

average case analysis is preferable, in probabalistic inputs since here we have a better understanding of how the data is distributed it will give you a more realistic time analysis.

In which situations is armortized analysis preferable to the other two analysis methods?

armortized analysis preferable, in dynamic arrays because it takes into consideration time complexity of operations accross the table, so if most of the operations are cheap and you get one thats relativley expensive, thus showing you that overall preformance can still be good.

Provide a step-by-step explanation of the binary search algorithm in your own words, and use a sample list to illustrate the process.

binary search is only for a sorted array. it searches the array from the middle so for example [0,1,2,3,4,5,6] the start is 3 since its the int in the middle and looks for a target number in this case we can say 5. since 5 > 3 we eliminate the left side. move to the right and repeat 4< 5 so we eliminate the left side and move to the right until we are at the target number which in this case after 4 we are now at 5.

Provide a step-by-step explanation of the selection sort algorithm in your own words, and use a sample list to illustrate the process.

selection sort is for unordered list and what it does is it goes through the list and selects the smallest element and appends it to a growing sorted list.

ex: [2,8,5,7,6] smallest-> [2] sorted list -> [2]

[8,5,7,6] smallest ->[5] sorted list ->[2,5]

[8,7,6] smallest -> [6] sorted list -> [2,5,6]

[8,7] smallest -> [7] sorted list -> [2,5,6,7]

[8] smallest -> [8] sorted list -> [2,5,6,7,8]

[] ------------------------------------->[2,5,6,7,8]

Given a sorted list lst of n distinct integers and an integer T, the goal is to determine the index of T if it exists in the list. If T is not present, find the index where it should be inserted to maintain the list’s sorted order. You must use binary search method.

def binary_search_i(lst, T):

left, right = 0, len(lst)-1

while left <= right:

mid = (left + right) // 2

if lst == T

return mid

elif lst[mid] < T:

left = mid + 1

else:

mid = right - 1

return left

Given a sorted list lst of n integers that may contain duplicates and a target integer T, find the first and last occurrence of T. If T is not found, return [−1, −1]. You must use binary search method.

lst = [3,1,4,4,4,4,7,6,2,5]

T = 4

def find_first_and_last(lst, T):

def binary_search(lst, T, find_first):

left, right = 0, len(lst) - 1

result = -1

while left <= right:

mid = (left + right) // 2

if lst[mid] == T:

result = mid

if find_first:

right = mid - 1

else:

left = mid + 1

elif lst[mid] < T:

left = mid + 1

else:

right = mid - 1

return result

first = binary_search(lst, T, find_first=True)

if first == -1: return [-1, -1] last = binary_search(lst, T, find_first=False)

return first, last

print(find_first_and_last(lst, T))