Двоичный поиск для нахождения вращения указывает в повернутом отсортированном списке

Вот изображение, иллюстрирующее предлагаемые алгоритмы:

Версия Delphi - третья улучшенная (благодаря коду polygenelubricants - еще одно сравнение удалено) вариант:

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;

Что-то вроде этого может сработать (не проверено):

//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;
}

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

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

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

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

Просто выполните метод деления пополам в списке - list [end] в диапазоне [1, end). Метод деления пополам ищет нули в функции путем поиска изменения знака и работает в 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, что соответствует вашей точке вращения.

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

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