Thiết lập chương trình cho công việc thường làm vào cuối giờ bán hàng: Cho trước số K (một doanh số giả định), cần tìm ra mặt hàng có doanh số nhỏ hơn K nhưng gần với K nhất. Bài toán này có thể sử dụng thuật toán tìm kiếm nào để giải?

Chương trình sử dụng thuật toán tìm kiếm nhị phân để tìm mặt hàng có doanh số nhỏ hơn K nhưng gần với K nhất trong danh sách mặt hàng đã được sắp xếp theo thứ tự tăng dần của doanh số.

def find_nearest_item(arr, K):

    # Sắp xếp danh sách mặt hàng theo thứ tự tăng dần của doanh số

    arr.sort()

    low, high = 0, len(arr) - 1

    result = None

    while low <= high:

        mid = (low + high) // 2 # Tính giá trị trung bình mid của low và high

        if arr[mid] < K:

            # Nếu giá trị doanh số của mặt hàng ở vị trí mid nhỏ hơn K

            # Đặt low = mid + 1 để tìm phần tử lớn hơn K

            low = mid + 1

        elif arr[mid] > K:

            # Nếu giá trị doanh số của mặt hàng ở vị trí mid lớn hơn K

            # Đặt high = mid - 1 để tìm phần tử nhỏ hơn K

            high = mid – 1

else:

            # Nếu giá trị doanh số của mặt hàng ở vị trí mid bằng K

            # Trả về mid làm kết quả

            result = mid

            break

        # Cập nhật giá trị gần K nhất

        if result is None or abs(arr[mid] - K) < abs(arr[result] - K):

            result = mid

    return arr[result]

# Example usage

arr = [10, 20, 30, 40, 50, 60, 70, 80, 90]

K = 45

nearest_item = find_nearest_item(arr, K)

print("Mặt hàng có doanh số nhỏ hơn K nhưng gần với K nhất là:", nearest_item)