Задан ориентированный взвешенный граф, содержащий, возможно, дуги отрицательного веса. Необходимо найти веса кратчайших путей от вершины v до всех остальных вершин.

В данной статье я реализую алгоритм бинарного поиска для массива int длины NMAX. Метод binary_search будет возвращать индекс элемента, если он существует и -1 в противном случае.

Нижеприведенная функция binarySearch производит бинарный поиск элемента х в массиве array. В качестве результата выдается индекс вхождения элемента х или -1, если элемент х не имеет вхождения в массив.

В массиве неотсортированных данных при отсутствии дополнительных фактов, поиск элемента по ключу осуществляется за O(n). В отсортированных данных возможно применение двоичного(бинарного поиска), который позволяет найти элемент по ключу за O(log(n)).

Дан взвешенный ориентированный граф из $N$ вершин. Требуется найти в нем величину кратчайшего пути между каждой парой вершин.

Функция kth(int l, int r, int k) находит k-ую порядковую статистику на отрезке [l;r] в массиве long long arr. Для этого используется модификация быстрой сортировки, только вместо того, чтобы сортировать весь массив, мы занимаемся поиском k-ого элемента в отсортированном массиве.

Функция kth(long[] array, int l, int r, int k) находит k-ую порядковую статистику на отрезка [l;r] массива array.

k-ой порядковой статистикой массива называется значение, которое будет стоять на k-ом месте после сортировки.

В данной статье мы реализуем цифровую сортировку на Java. В среднем цифровая сортировка работает лучше чем быстрая сортировка.

Дан взвешенный ориентированный граф из $N$ вершин и $M$ дуг. В графе могут быть как петли, так и дуги отрицательного веса. Требуется найти расстояние от первой вершины до всех остальных.