Unit 2

Solution a): Linear search

Explanation: Linear search starts from the first element, which in this case happens to be 110. Therefore here linear search will immediately return the first element. We can only do binary search on sorted lists, which means binary search is not a valid option for searching through this list.

Solution b): Linear search

Explanation: We can only do binary search on sorted lists, which means binary search is not a valid option for searching through this list.

Solution c): Binary search

Explanation: Here, binary search will be much faster (best case scenario for binary search) since the target element is the middle element of the list and will be found on the first run, giving it an O(1) complexity for this particular case.

Solution d): Linear search

Explanation: We can only do binary search on sorted lists, which means binary search is not a valid option for searching through this list.

Solution e): Binary Search

Explanation: Since this list does not contain 110, if we were to run linear search it would check all the elements in the list and return False at the end, giving it a complexity of O(n). This is the worst case for linear search. Binary search on the other hand will only need to check thrice (79 as the first middle element and 200 as the second and 130 at the end) and then it will return false. This is because binary search halves the search with every check and runs in O(logn), so faster than linear search.

Using linear search: We'll check each element one by one until we find it, starting from the first element.

Search Order: 1, 5, 6

Using binary search: We'll repeatedly find the middle element, compare it to the number we are looking for and determine whether the target value is in the first (if target is less than the middle value) or second half (if target is greater than the middle value) of the list, continuing our search in only one half of the list.

Search order: 10, 5, 6

Function Calls for Target 11

binarySearch([0, 3, 5, 8, 9, 10 11, 14, 17], 11)

binarySearch([10 11, 14, 17], 11)

binarySearch([10 11], 11)

Function Calls for Target 7

binarySearch([0, 3, 5, 8, 9, 10 11, 14, 17], 7)

binarySearch([0, 3, 5, 8], 7)

binarySearch([8], 7)

binarySearch([], 7)

Solution:

Binary Search: O(log n)

Searches a sorted list by repeatedly dividing the list in half, resulting in a log runtime.

Linear Search: O(n)

Checks each element in a list until the target value is found, resulting in a linear runtime.

Solution:

Linear Search: The worst-case scenario for linear search happens when the target element is either not in the list or is at the end. It has a time complexity of O(n), where n is the number of elements in the list (it would need to search the whole list).

Binary Search: The worst-case scenario for binary search occurs when the target element is either not in the sorted array or is at one end, and the array cannot be evenly divided. It has a time complexity of O(log n), where n is the number of elements in the sorted array.

Solution:

Linear Search: The best-case scenario for linear search is when the target element is found in the first position of the list. Time complexity would be O(1), constant time.

Binary Search: The best case for binary search is when the target element is the middle element of the list. The time complexity would be O(1), constant time.

 
def checkAny(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return True
    return False
        
def checkAll(lst, target):
    for i in range(len(lst)):
        if lst[i] != target:
            return False
    return True
    

Solution:

Search follows a common pattern for functions that use a loop to return a Boolean.

A check-any pattern returns True if any of the items in the list meet a condition, and False otherwise. Namely, the first time the condition becomes true, we return True immediately, stop the iteration and exist the function. If we never make the if condition True, that means we have iterated over all elements, and we return False in the end.

A check-all pattern returns True if all of the items in the list meet a condition, and False otherwise. Namely, the first time the condition becomes true, we return False immediately, stop the iteration and exist the function. If we never make the if condition True, that means we have iterated over all elements, and we return True in the end.

# Prints instructions to solve Towers of Hanoi and
# returns the number of moves needed to do so.
def moveDiscs(start, tmp, end, discs):
 if discs == 1: # 1 disc - move it directly
    print("Move one disc from", start, "to", end)
    return 1
 else: # 2+ discs - move N-1 discs, then 1, then N-1
    moves = 0
    moves = moves + moveDiscs(start, end, tmp, discs - 1)
    moves = moves + moveDiscs(start, tmp, end, 1)
    moves = moves + moveDiscs(tmp, start, end, discs - 1)
    return moves

result = moveDiscs("left", "middle", "right", 3)

Solution:

• The first call to moveDiscs with discs == 3 enters the recursive case makes three recursive calls:
  • moveDiscs("left", "right", "middle", 2)
  • moveDiscs("left", "middle", "right", 1) ← will return 1 as it will hit the base case
  • moveDiscs("middle", "left", "right", 2)
• Each of the discs == 2 calls then triggers further recursive calls until discs == 1, at which point it prints the move and returns 1.
  • moveDiscs("left", "right", "middle", 2) triggers another set of recursive calls:
    • moveDiscs("left", "middle", "right", 1) ← will return 1
    • moveDiscs("middle", "left", "right", 1) ← will return 1
    • moveDiscs("left", "right", "middle", 1) ← will return 1
• Then each moveDiscs("left", "right", "middle", 2) call will return 3, we can trace back to our above code and get the following:
  • moveDiscs("left", "right", "middle", 2) ← will return 3
  • moveDiscs("left", "middle", "right", 1) ← will return 1 as it will hit the base case
  • moveDiscs("middle", "left", "right", 2) ← will return 3
• Then we know that moveDiscs("left", "middle", "right", 3) will return 7 (3 + 3 + 1). So the value of result will be 7.

Solution:

def linearSearch(L, n):
  # Base Case: We know that if the list is empty then n cannot be in the list --> return None
  if L == []:
    return None
  
  # Recursive Case:
  else:
    # if the first element is the target element, we can simply return the target
    if L[0] == n:
      return n
    # Otherwise we continue to search through the rest of the list recursively
    return linearSearch(L[1:], n)

Solution:

def binarysearch(L, item):
    if len(L) == 0:
        return False
    mid = len(L)//2
    if L[mid] == item:
        return True
    elif L[mid] > item:
        return binarysearch(L[:mid],item)
    else:
        return binarysearch(L[mid+1:],item)