Двоичный поиск, чтобы найти точку вращения в повернутом отсортированном списке

У меня есть отсортированный список, который вращается и хотел бы выполнить бинарный поиск в этом списке, чтобы найти минимальный элемент.

Предположим, что начальный список {1,2,3,4,5,6,7,8} может быть повернут как {5,6,7,8,1,2,3,4}

Обычный бинарный поиск в этом случае не работает. Есть идеи как это сделать.

-- Редактировать

У меня есть еще одно условие. Что делать, если список не отсортирован?

 Maciej Hehl10 мая 2010 г., 04:55
Как я и думал. Проблема с Java :) Спасибо.
 Maciej Hehl10 мая 2010 г., 04:40
Я единственный, кто, когда читает «список», думает о структуре данных, которая не поддерживает произвольный доступ?
 polygenelubricants10 мая 2010 г., 04:52
@Maciej: даже если вы не единственный, это все равно неверный вывод. В JavaArrayList<E> implements List<E>, RandomAccess, С другой стороны,LinkedList<E> не являетсяRandomAccess.

Ответы на вопрос(10)

Просто выполнитеметод деления пополам наlist - list[end] в диапазоне [1, конец). Метод деления пополам ищет нули в функции путем поиска изменения знака и работает в O (log n).

Например,

{5,6,7,8,1,2,3,4} -> {1,2,3,4, -3, -2, -1,0}

Затем используйте (дискретизированный) метод деления пополам в этом списке {1,2,3,4, -3, -2, -1}. Он найдет пересечение нуля между 4 и -3, что соответствует вашей точке вращения.

Вот картинка для иллюстрации предложенных алгоритмов:

 Moha the almighty camel25 мар. 2016 г., 21:31
это лучший ответ: «дай человеку рыбу, и ты накормишь его на день; научи человека ловить рыбу, и ты накормишь его на всю жизнь»
 Boolean09 мая 2010 г., 22:16
Это было очень полезно. Спасибо @tjr.
Решение Вопроса

Небольшая модификация алгоритма двоичного поиска - все, что вам нужно; вот решение в полностью работоспособной Java (см.Ответ серга для реализации Delphi, иответ ткр для наглядного объяснения алгоритма).

import java.util.*;
public class BinarySearch {
    static int findMinimum(Integer[] arr) {
        int low = 0;
        int high = arr.length - 1;
        while (arr[low] > arr[high]) {
            int mid = (low + high) >>> 1;
            if (arr[mid] > arr[high]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    public static void main(String[] args) {
        Integer[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        // must be in sorted order, allowing rotation, and contain no duplicates

        for (int i = 0; i < arr.length; i++) {
            System.out.print(Arrays.toString(arr));
            int minIndex = findMinimum(arr);
            System.out.println(" Min is " + arr[minIndex] + " at " + minIndex);
            Collections.rotate(Arrays.asList(arr), 1);
        }
    }
}

Это печатает:

[1, 2, 3, 4, 5, 6, 7] Min is 1 at 0
[7, 1, 2, 3, 4, 5, 6] Min is 1 at 1
[6, 7, 1, 2, 3, 4, 5] Min is 1 at 2
[5, 6, 7, 1, 2, 3, 4] Min is 1 at 3
[4, 5, 6, 7, 1, 2, 3] Min is 1 at 4
[3, 4, 5, 6, 7, 1, 2] Min is 1 at 5
[2, 3, 4, 5, 6, 7, 1] Min is 1 at 6
Смотрите такжеJava Collections.rotate () с массивом не работаетОбъясняет почемуInteger[] вместоint[]Блог исследований Google: почти все двоичные поиски и слияния нарушеныОбъясняет почему>>> 1 вместо/ 2На дубликаты

Обратите внимание, что дублирование делает невозможным это вO(log N), Рассмотрим следующий битовый массив, состоящий из множества1, и один0:

  (sorted)
  01111111111111111111111111111111111111111111111111111111111111111
  ^

  (rotated)
  11111111111111111111111111111111111111111111101111111111111111111
                                               ^

  (rotated)
  11111111111111101111111111111111111111111111111111111111111111111
                 ^

Этот массив можно вращать вN пути и локализация0 вO(log N) невозможно, так как невозможно определить, находится ли он слева или справа от «середины».

У меня есть еще одно условие. Что делать, если список не отсортирован?

Затем, если вы не хотите сначала отсортировать и продолжить, вам придется выполнить линейный поиск, чтобы найти минимум.

Смотрите такжеВикипедия | Алгоритм выбора | Линейный минимум / максимум алгоритмы
 Ritsaert Hornstra09 мая 2010 г., 09:12
+1 за упоминание проблемы дубликатов.
 kludg09 мая 2010 г., 09:48
-1 Не кради код без ссылок
 KGhatak09 нояб. 2016 г., 19:51
@ polygenelubricants - ИМХО, идея бинарного поиска будет работать, только если отсортированная последовательность строго увеличивается. Например, для входа {2,3,3,4,4,2,2} ожидаемое (предположим, по часовой стрелке) вращение равно 5, но приведенный выше код скажет нам «Min is 2 at 0». Может быть, вы могли бы прямо упомянуть предположение.
 polygenelubricants10 мая 2010 г., 05:39
@Serg: я удалил свои комментарии; политика и драма идут в мета (meta.stackexchange.com/questions/49383/...)
 eold23 февр. 2011 г., 15:13
Не будет ли правильнее заменить линию(low + high) >>> 1; с(low + high - 1) >>> 1 ? Это отбрасывает кандидатов быстрее. Более того, я попытался изменить этот код, чтобы найти лучший элемент, и в этом случае(low + high + 1) >>> 1 это единственный правильный выбор. Смотри мою темуstackoverflow.com/questions/4844165/... для деталей.

Рекурсия очень хороша, если мы хотим сохранить простоту и удобочитаемость кода. Но если нам удастся избежать рекурсии и при этом сохранить читабельность, было бы лучше, потому что стоимость рекурсии значительна и фактически не масштабируется.

Вот простойитеративный метод с логикой, как описано выше (он использует преимущества бинарного поиска, добавляя небольшую логику раздела).

private static int partitionSearch(int[] sortedArray, int numToFind) {
    if(sortedArray[0] > numToFind && sortedArray[sortedArray.length -1 ] < numToFind)
        return -1;
    boolean isInFirstPartition = sortedArray[0] <= numToFind;

    int startIndex = 0;
    int endIndex = sortedArray.length -1;
    int currentIndex;
    int currentValue;
    if(isInFirstPartition) { 
        do {
            currentIndex = (startIndex + endIndex) / 2;
            currentValue = sortedArray[currentIndex];
            if(currentValue == numToFind)
                return currentIndex;
            if(currentValue > sortedArray[startIndex] && sortedArray[currentIndex] < numToFind)
                startIndex = currentIndex + 1;
            else
                endIndex = currentIndex - 1;
        } while (startIndex <= endIndex);
    } else {
        do {
            currentIndex = (startIndex + endIndex) / 2;
            currentValue = sortedArray[currentIndex];
            if(currentValue == numToFind)
                return currentIndex;
            if(currentValue < sortedArray[endIndex] && sortedArray[currentIndex] > numToFind)
                endIndex = currentIndex - 1;
            else
                startIndex = currentIndex + 1;
        } while (startIndex <= endIndex);
    }
    return -1;
}
 raam8601 окт. 2012 г., 01:08
«... если мы можем избежать этого и при этом сохранить читабельность, это должно быть хорошо».

Версия Delphi - третий улучшенный (благодаря коду полигеномасляных веществ - еще одно сравнение удалено):

type
  TIntegerArray = array of Integer;

function MinSearch(A: TIntegerArray): Integer;
var
  I, L, H: Integer;

begin
  L:= Low(A);   // = 0
  H:= High(A);  // = Length(A) - 1
  while A[L] > A[H] do begin
    I:= (L + H) div 2; // or (L + H) shr 1 to optimize
    Assert(I < H);
    if (A[I] > A[H])
      then L:= I + 1
      else H:= I;
  end;
  Result:= A[L];
end;

Выберите некоторую подпоследовательность[i,j] из списка[first, last), Или[i,j] не содержит разрыв, в этом случае*i <= *jили это так, и в этом случае остальные элементы(j, last) U [first, i), правильно отсортированы, в этом случае*j <= *i.

Рекурсивно разделите подозрительный диапазон до тех пор, пока вы не опуститесь до одного элемента. Принимает O (log N) сравнений.

В C ++ 11 эту проблему можно решить с помощьюpartition_point:

std::vector<int> arr = {5,6,7,8,1,2,3,4};
auto rotation_point = std::partition_point(arr.begin(), std::prev(arr.end()),
    [&arr](int elem) { return elem > arr.back(); });

Я хотел бы сделать бинарный поиск в этом списке, чтобы найти минимальный элемент.
Тройной поиск будет работать для такого случая: когда функция имеет ровно один локальный минимум.

http://en.wikipedia.org/wiki/Ternary_search

редактировать При втором чтении я, вероятно, неправильно понял вопрос: функция не соответствует требованиям для троичного поиска: / Но не будет ли работать двоичный поиск? Предположим, оригинальный заказ увеличивался.

if (f(left) < f(middle)) 
    // which means, 'left' and 'middle' are on the same segment (before or after point X we search)
    // and also 'left' is before X by definition
    // so, X must be to the right from 'middle'
    left = middle
else
    right = middle
 Nikita Rybak09 мая 2010 г., 05:19
@ Билли ONeal И похоже, что вы отправили тот же алгоритм :)
 Billy ONeal09 мая 2010 г., 05:09
Прямой двоичный поиск не работает, потому что список был повернут.
 Nikita Rybak09 мая 2010 г., 05:16
Обратите внимание, что бинарный поиск в его традиционной форме ищет определенное значение, а не минимум функции. Таким образом, «традиционные условия» тоже не могут быть применены. Во всяком случае, я добавил комментарий в коде, чтобы объяснить логику.

Моя версия реализации алгоритма бинарного поиска вДжава:

/**
 * Works only for arrays with NO duplicates.
 * Work also for zero-shifted array, e.g fully sorted, when shift = 0.
 */
public static int searchInShiftedArr(int[] arr, int key) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int low = 0;
    int high = arr.length - 1;
    int mid; // declared outside loop to avoid constant memory allocation for this variable
    while (low <= high) {
        mid = (low + high) >>> 1; // same as "(low + high) / 2", but avoid negative overflow and should be faster than "low + (high - low)/2"
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[low] <= arr[mid]) { // means left half of the array is sorted
            if (arr[low] <= key && key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else { // means right half of the array is sorted
            if (arr[mid] < key && key <= arr[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

Кодуспешно прошел 5000 тестовых случаевтак что я думаю, что производство готово.

Примерно так может работать (не проверено):

//assumes the list is a std::vector<int> myList

int FindMinFromRotated(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
    if (begin == end)
        throw std::invalid_argument("Iterator range is singular!");
    if (std::distance(begin, end) == 1) //What's the min of one element?
        return *begin;
    if (*begin < *end) //List is sorted if this is true.
        return *begin;
    std::vector<int>::iterator middle(begin);
    std::advance(middle, std::distance(begin, end)/2);
    if (*middle < *begin) //If this is true, than the middle element selected is past the rotation point
        return FindMinFromRotated(begin, middle)
    else if (*middle > *begin) //If this is true, the the middle element selected is in front of the rotation point.
        return FindMinFromRotated(middle, end)
    else //Looks like we found what we need :)
        return *begin;
}

Ваш ответ на вопрос