CompSci 260P: Week 8

• Let be an unsorted array of integers
• A local minimum satisfies the condition
• Provide an efficient algorithm that finds the local minimum

• There must exist a local minimum!
  • and
  • So long as this property holds for your subarray, then a local minimum must exist
• Suppose we make a comparison between
  • If it holds, we found the solution!
  • If ...
  • We can replace with !
• Binary Search!

def binary_search(array):
    left, right = 0, len(array)
    while left < right:
        mid = (left + right) // 2
        if condition(array[mid]):
            right = mid
        else:
            left = mid + 1
    return left

def binary_search(A):
    left, right = 1, len(A) - 1
    while left < right:
        mid = (left + right) // 2
        if A[mid - 1] < A[mid]:
            right = mid - 1
        elif A[mid] > A[mid + 1]:
            left = mid + 1
        else:
            return mid

    return left

• Analysis looks identical to that of Binary Search

• Given keycards, each with an ID
• Cannot read the ID, only able to check if two keycards match
• Keycard is a majority card if there is strictly more than cards which match
• Design a algorithm that can determine whether there is a majority card

• Imagine if we split the array in half
  • Pigeonhole Principle: Majority card must also be majority of at least one half
• Don't know which half contains the true majority card
  • Recursion may find for us the majority keycard of each half
• We may be provided at most 2 candidate majority cards
  • For each candidate majority card, check if it truly is a majority card
  • Return if there is, otherwise return false

• The algorithm makes recursive subcalls, each of size
• Checking the candidates takes time