Допустим, у меня есть n блоков, где внутри каждого блока есть какое-то значение b[i]. Я могу гарантировать, что массив ящиков отсортирован так, что b[1] <= b[2] <= ... <= b[n]. Я также могу гарантировать, что есть элемент b[i] = x, и я хотел бы выяснить, в каком ящике x находится. Проблема в том, что открытие каждого ящика b[i] имеет определенную стоимость c[i].
Проблема в том, как минимизировать общую стоимость поиска x? Мой интуитивный подход заключается в выполнении бинарного поиска на b[i]. Это уменьшает общее количество операций (так как я получаю это O (logn) сравнения), но я не могу точно понять, как это минимизирует общую стоимость.
Очевидно, что просто выбрать самую дешевую коробку и продолжить не получится, поскольку в худшем случае я бы открывал каждую коробку. Любые идеи о том, как я мог бы улучшить это или как я могу доказать, что мой подход является оптимальным / не оптимальным?