java - pseint - Búsqueda binaria para encontrar el punto de rotación en una lista ordenada rotativa

busqueda binaria pseint

Question

Tengo una lista ordenada que se rota y me gustaría hacer una búsqueda binaria en esa lista para encontrar el elemento mínimo.

Supongamos que la lista inicial es {1,2,3,4,5,6,7,8} La lista girada puede ser como {5,6,7,8,1,2,3,4}

La búsqueda binaria normal no funciona en este caso. Alguna idea de cómo hacer esto.

- Editar

Tengo otra condición. ¿Qué pasa si la lista no está ordenada?

Answer 1

Algo como esto podría funcionar (No probado):

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

Answer 2

Elija alguna subsecuencia [i,j] de la lista [first, last) . O bien [i,j] no contiene la discontinuidad, en cuyo caso *i <= *j , o lo hace, en cuyo caso los elementos restantes (j, last) U [first, i) , están correctamente ordenados, en los cuales caso *j <= *i .

Dividen bipartición recursiva en el rango sospechoso hasta que descifre hasta un elemento. Toma comparaciones O (log N).

Answer 3

Simplemente realice el método de bisección en la list - list[end] sobre el rango [1, final). El método de bisección busca ceros en una función buscando un cambio de signo y opera en O (log n).

Por ejemplo,

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

Luego use el método de bisección (discretizado) en esa lista {1,2,3,4, -3, -2, -1}. Encontrará un cruce por cero entre 4 y -3, que corresponde a su punto de rotación.

Answer 4

Versión de Delphi - tercera variante mejorada (gracias al código de los poligeneles lubricantes: una comparación más)

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;

Answer 5

Me gustaría hacer una búsqueda binaria en esa lista para encontrar el elemento mínimo.
La búsqueda ternaria funcionará para ese caso: cuando la función tiene exactamente un mínimo local.

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

editar En la segunda lectura, probablemente entendí mal la pregunta: la función no cumple los requisitos para la búsqueda ternaria: / ¿Pero no funcionará la búsqueda binaria? Supongamos que el orden original aumentara.

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

Answer 6

Mi versión de la implementación del algoritmo de búsqueda binaria en 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;
}

El código pasó con éxito 5000 TestCases , así que creo que está listo para producción.

Answer 7

La recursividad es muy buena si queremos mantener la simplicidad y la legibilidad del código. Pero si podemos evitar la recursión y aún mantener la legibilidad, sería mejor porque el costo de la recursión es significativo y, en realidad, no es escalable.

Aquí hay un método iterativo simple con lógica, tal como se discutió anteriormente (se está aprovechando la búsqueda binaria, agregando una pequeña lógica de partición).

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

Answer 8

En C ++ 11, este problema se puede resolver con 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(); });

Answer 9

Aquí hay una imagen para ilustrar los algoritmos sugeridos:

Answer 10

Una ligera modificación en el algoritmo de búsqueda binaria es todo lo que necesita; esta es la solución en Java ejecutable completo (ver la respuesta de Serg para la implementación Delphi y la respuesta de tkr para la explicación visual del algoritmo).

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

Esto imprime:

[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

Ver también

• Java Collections.rotate () con una matriz no funciona
  • Explica por qué Integer[] lugar de int[]
• Blog de Google Research: casi todas las búsquedas binarias y Mergesorts están rotas
  • Explica por qué >>> 1 lugar de / 2

En duplicados

Tenga en cuenta que duplicados hace que sea imposible hacer esto en O(log N) . Considere la siguiente matriz de bits que consta de muchos 1 y un 0 :

  (sorted)
  01111111111111111111111111111111111111111111111111111111111111111
  ^

  (rotated)
  11111111111111111111111111111111111111111111101111111111111111111
                                               ^

  (rotated)
  11111111111111101111111111111111111111111111111111111111111111111
                 ^

Esta matriz se puede rotar en N maneras, y ubicar el 0 en O(log N) es imposible, ya que no hay manera de saber si está en el lado izquierdo o derecho del "medio".

Tengo otra condición. ¿Qué pasa si la lista no está ordenada?

Luego, a menos que desee ordenar primero y continuar desde allí, tendrá que hacer una búsqueda lineal para encontrar el mínimo.

Ver también

• Wikipedia | Algoritmo de selección | Algoritmos mínimos / máximos lineales