Binary Search

Question 1

Implement

Special Binary Search that will return the number of elements in arr that are <= target

Input: arr and target
Output: count of how many elements are <= target

Answer 1

def binary_search_count_leq_target(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1

    return left

The output here is NOT meant to be used an index for arr since left can be equal to len(arr) if all the elements in arr are <= target

Question 2

Implement

Special Binary Search that will return the index of the highest element that is <= target

Input: arr and target
Output: index of the highest value that is <= target

Answer 2

def binary_search_floor(arr, target):
    left, right = 0, len(arr) - 1
    result = -1  # -1 if no value <= target exists

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            result = mid     # potential candidate, look further right
            left = mid + 1
        else:
            right = mid - 1

    return result

Question 3

Implement

Special Binary Search that will return the index of the lowest element that is >= target if it exists

Input: arr and target
Output: index of the lowest value that is >= target; return -1 if all values in arr are < target

Answer 3

def binary_search_ceiling_quick(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1

    return left if left < len(arr) else -1

Notice that this is nearly identical to the Binary Search method that counts elements that are <= target. The difference is just the last line that will prevent “left” from return an out of bounds value. If “left” reaches len(arr), it means all values in arr are < target

Question 4

Implement

Special Binary Search that will return the index of the lowest element that is > target if it exists

Input: arr and target
Output: index of the lowest value that is > target; return -1 if all values in arr are <= target

Answer 4

def binary_search_strict_upper(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    return left if left < len(arr) else -1

Notice that this is nearly identical to the Binary Search method that returns the index of the lower element that is >= target (gte vs just gt in this solution). The difference is the comparison used

Question 5

Special Binary Search that will return the number of elements in arr that are <= target BUT the elements are in reverse (non-increasing / decreasing) order

Input: arr and target
Output: count of how many elements are <= target

Answer 5

def binary_search_reverse(arr, target):
    lo, hi = 0, len(arr)  -1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if -(arr[mid]) <= target:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo