Wataru

if i == middle - 1 or i >= 5 and len(list) <= 4:
            return -1

Вот эта часть вызвает вопросы. Отладочный код остался?

Проблема в вашем коде, что он виснет, если числа в массиве вообще нет. Условие должно быть не про равенство, а про то, что у вас отрезок пуст (или длины 1) - надо сравнивать first и last.

Обычно middle не поддерживают между итерациями цикла, а просто считают внутри. Между итерациями переходят только first и last.

А так, да, бинпоиск - это весьма простой алгоритм.

В сетевом роутинге, в основном, нет* центрального узла с информацией о всей топологии, чтобы искать пути. Так что там вообще не работает Дейкстра, а работают распределенные алгоритмы.

А так, да, на очень специфичных гарфах всеядный алгоритм Дейкстры не самый лучший вариант. И ваш алгоритм тут получается быстрее.

* Вообще, есть такая тема, как Software Defined Networking, где как раз есть центральный узел, который все и решает, но это чисто теория пока, и там суть не в поиске кратчайших путей в графе а во всяких сложных механизмах приоритезации трафика и устойчивости к сбоям.

Можно целочисленным линейным программированием решать. Бинплиском перебтрайте ответ (k), потом составляйте задачу, где у вас переменные: сколько монет каждого типа берём в каждый из k разменов. И еще будут неравенства, что каждый тип монет используется суммарно не больше, чем есть монет. Целевая функция - любая.

Еще можно чуть по-другому: находите переблром все варианты одного размена. Потом у вас переменные будут, сколько раз каждый из вариантов берете. Ограничения на общий расход каждой монеты, а целевая функция - сумма переменных. Тут нет бинплиска, но тоже ЦЛП.

Вообще, преобразование из double в int - это не ошибка. Это warning (и то, он выводится, только если компилятору указать -Wconversion. Код выше этот варнинг выдает во втором месте, но все-равно компилируется.

Если у вас преобразование умышленное, и вы знаете, что там не будет ошибки переоплнения, то вы можете использовать static_cast тогда компилятор не будет выдавать предупреждение.

Вам надо в вашем алгоритме еще завести словарь, куда вы для каждой вершины будете складывать предыдущую в пути. Там, где вы соседнюю вершину кладете в очередь - там надо сарзу смотреть, посещенная она или нет и класть только если нет. Вот в этот момент вы знаете, что вы пришли в graph[city][i] из city.

В конце циклом по этому массиву пердыдущих вершин пройдитесь и так получите путь в обратном порядке.

Ну нет его в стандартной библиотеке, как и длинных чисел. Используйте gmplib, например.

Потому что это 2 разных графика, 2 разных примера. Могли бы на втором обозвать вместо f и g f` и g`. Но авторам, наверно, было лень.

Для такой вот работы идеально подходят связные списки. Там можно менять объект не портя никакие итераторы. Проблема только в том, что связные списки в питоне не реализованы на уровне языка. Поищите реализацию, наверняка есть удобный модуль со списками.

Еще можноиспользовать обычный list, только вы итерируйтесь циклом while и используйте индексы:

i = 0
while i < len(arr):
  x = arr[i]
  j = i+1
  while j < len(arr):
    if ShouldDelete(arr[j], arr[i]):
      del a[j]

Это будет в n раз медленнее, к сожалению. Можно наверно слайсами сделать быстрее:

arr[i+1:] = y for y in arr[i+1:] if not ShouldDelete(x, arr[i])

Я не питонист и возможно ошибку допустил. И мне этот код не кажктся очень понятным, но возможно это истиный путь для питона.

А так, в общем случае, идет двойная итерация с пометками элементов на удаление.

Какого-то названия этот прием не имеет, ибо это костыль для конкретных реализаций контейнеров.

Теоретически - да. Специализированный движок лишь для вашей игры будет быстрее и легче многофункционального комбайна UE. На практике у вас там объем работы будет на сотню человеко-лет.

Подсказка: вот то число, что у вас в конце выводится - это 2^64-1. Еще подсказка: size_t на современных платформах имеет размер 64 бита.

У вас переполнение. Вы там из 0 вычитаете 1 в итерации цикла, получаете самое большое число, представимое в 64-битном типе.

Надо переписать цикл на while и делать из него break по достижению 0. Или тип переменной сменить на знаковый.

Занумеруйте все биты от 0 до 16. Потом транспонируйте эту матрицу. Потом посмотрите на разность результата и конца. Вот эти вот числа - это на сколько бит надо сдвинуть исходные биты, чтобы они встали на нужное место.

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

0 4 8 12
1 5 9 13
2 6 10 13
3 7 11 15

0 -3 -6 -9
3 0 -3 -6
...

Все биты с одинаковым смещением можно подсчитать за 3 операции: Сдвиг, битовая маска и побитовое или в ответ.
Я тут вижу 7 разных чисел -9,-6,-3,0,3,6,9.
Например, для 0 и 3 у вас будет

answer = (source & 0x1248) | ((source << 3) | 0x2480) | ...

Это не 8 пока еще операций, а аж 20. Возможно можно как-то еще их сгруппировать.

Edit: Возможно, еще подход с таблицей будет быстрее. Для каждого из 16 возможных значений строк выдавайте битовое число - столбец, где эти 4 бита на позициях 0, 4, 8,12. Тогда ответ будет table[source&0xf0] | (table[(source>>4)&0xf] << 1) | (table[(source>>8)&0xf] << 2) | (table[(source>>12)&0xf] << 3).

Тут 13 битовых операций и 4 чтения из памяти.