Binary Search

Testing code snippets

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2  # Find middle index
        print(f"Searching between indices {left} and {right}, middle index is {mid}, value at mid is {arr[mid]}")
        if arr[mid] == target:
            return mid, arr[mid]  # Return index and the value at mid
        elif arr[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half
    return -1, None  # Element not found

# Example usage:
arr = [1, 3, 5, 7, 9, 11, 13]
target = 3
index, value = binary_search(arr, target)
print(f"Target found at index {index}, value is {value}")

Searching between indices 0 and 6, middle index is 3, value at mid is 7
Searching between indices 0 and 2, middle index is 1, value at mid is 3
Target found at index 1, value is 3

Homework Hacks

Homework Hack 1

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2  # Find middle index
        print(f"Searching between indices {left} and {right}, middle index is {mid}, value at mid is {arr[mid]}")
        if arr[mid] == target:
            return mid, arr[mid]  # Return index and the value at mid
        elif arr[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half
    return -1, None  # Element not found

# input
input_arr = [4, 5, 6, 7, 0, 1, 2]
input_target = 1

input_arr.sort()
output = binary_search(input_arr, input_target)
print(f"Element {input_target} is at index: {output}")

7
[4, 5, 6, 7, 0, 1, 2]
Searching between indices 0 and 6, middle index is 3, value at mid is 7
Searching between indices 0 and 2, middle index is 1, value at mid is 5
Searching between indices 0 and 0, middle index is 0, value at mid is 4
Element 1 is at index: (-1, None)

Note: Your answer to the homework is wrong.

The answer says 5 on the homework, but that is unsorted if you actually sort the array and get the index the answer is 1.

Homework Hack 2

def find_first_and_last(arr, target):
    def find_index(is_first):
        left, right = 0, len(arr) - 1
        index = -1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                index = mid
                if is_first:
                    right = mid - 1
                else:
                    left = mid + 1
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return index

    first = find_index(is_first=True)
    last = find_index(is_first=False)
    return (first, last)

arr = [1, 2, 2, 2, 3, 4, 5]
target = 2
print(find_first_and_last(arr, target))

(1, 3)

Homework Hack 3

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

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

    return result

arr = [1, 3, 5, 7, 9, 11]
target = 8
print(smallest_greater_or_equal(arr, target))

9