Принцип достаточно прост - делаем два указателя и пускаем их по списку с разной скоростью. Первый медленный или черепаха идет по каждому узлу списка, а второй, быстрый Заяц - скачет через один.
Что из этого можно получить?
В магию математики погружаться не будем...
Если заяц доскакал до конца, то черепаха будет как раз на середине. Красота!
Возвращаем указатель "черепаха" вот вам и решение задачи.
Опять запускаем наших животных и ждем когда они встретятся. А они точно встретятся (магия математики).
Т.е. если последний узел зациклен на любой из узлов списка, то заяц обязательно войдет в цикл и догонит черепаху.
И вот если два указателя показывают на одно и то же место, то список однозначно зациклен.
Если наш список зациклен, то исходя их пункта 2 мы можем узнать где "встретились" черепаха и заяц.
А дальше опять магия, если начать движение по каждому следующему узлу от головы списка и от точки встречи, то точка пересечения, т.е. когда оба указателя дойдут до одного узла, то этот узел и будет первым узлом цикла.
Не верите, проверьте! Магия работает!!!
Ну тут совсем просто, нашли первый узел цикла, и топаем дальше пока не найдем узел который на него ссылается. Вот вам и последний элемент.
И еще парочка задач, когда дано два списка
Тут сначала проходим эти списки до конца, если конец один и тот же элемент значит пересекаются.
А тут опять магия, берем "хвост" и зацикливаем его на одну из голов.
А со второй ищем первую точку цикла - которая и есть точка пересечения.
Только после не забывайте убрать цикл с хвоста, что бы чего не вышло...
Основная мысль бинарного поиска заключается в эффективном нахождении заданного элемента в упорядоченном массиве данных. Основная идея состоит в том, чтобы разделить массив пополам и проверить, находится ли искомый элемент в левой или правой половине массива. Затем процесс повторяется для выбранной половины, пока не будет найден искомый элемент или пока не останется только один элемент в массиве.
Основной алгоритм бинарного поиска:
Пока low не превышает high, выполните следующие шаги:
Бинарный поиск работает ТОЛЬКО на отсортированных массивах.
Пример кода:
public static int binarySearch (int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}