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

Ответ 1

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

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 Research: почти все двоичные поиски и слияния не найдены
  • Объясняет, почему >>> 1 вместо / 2

О дубликатах

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

  (sorted)
  01111111111111111111111111111111111111111111111111111111111111111
  ^

  (rotated)
  11111111111111111111111111111111111111111111101111111111111111111
                                               ^

  (rotated)
  11111111111111101111111111111111111111111111111111111111111111111
                 ^

Этот массив можно повернуть в N способами, а расположение 0 в O(log N) невозможно, так как нет способа определить, находится ли он в левой или правой части "среднего".

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

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

См. также

• Википедия | Алгоритм выбора | Линейные алгоритмы минимума/максимума

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

Версия 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;

Ответ 7

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

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

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

Ответ 8

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

/**
 * 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 TestCases, поэтому я думаю, что это готово к производству.

Ответ 9

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

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

Ответ 10

В С++ 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(); });