"""TutorSyntax v25: search and sort starter (Python 3, standard library only)."""

values = [3, 7, 12, 18, 25, 31, 42, 56]  # Sorted: binary search needs this.

def linear_search(items, target):
    """Return the index of target, or -1 if it cannot be found."""
    for index, value in enumerate(items):
        if value == target:
            return index
    return -1

def binary_search(items, target):
    """Halve the search range until target is found or the range is empty."""
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def bubble_sort(items):
    """Return a new sorted list, leaving the original untouched."""
    answer = items.copy()
    for end in range(len(answer) - 1, 0, -1):
        swapped = False
        for index in range(end):
            if answer[index] > answer[index + 1]:
                answer[index], answer[index + 1] = answer[index + 1], answer[index]
                swapped = True
        if not swapped:
            break
    return answer

if __name__ == "__main__":
    for number in [25, 56, 99]:
        print(number, "linear:", linear_search(values, number), "binary:", binary_search(values, number))
    print("Sorted:", bubble_sort([7, 3, 9, 1, 5, 8]))
    # Challenge: count comparisons for each search method.