algorithm - tipos - que es una matriz en programacion

Buscando un elemento en una matriz ordenada circular

Question

Queremos buscar un elemento dado en una matriz ordenada circular en complejidad no mayor que O(log n) .
Ejemplo: Buscar 13 en {5,9,13,1,3} .

Mi idea fue convertir la matriz circular en una matriz ordenada regular y luego hacer una búsqueda binaria en la matriz resultante, pero mi problema fue que el algoritmo que encontré fue una estupidez que requiere O(n) en el peor de los casos:

for(i = 1; i < a.length; i++){
    if (a[i] < a[i-1]){
        minIndex = i; break;
    }
}

entonces el índice correspondiente del elemento i se determinará a partir de la siguiente relación:

(i + minInex - 1) % a.length

está claro que mi algoritmo de conversión (de circular a regular) puede tomar O (n), por lo que necesitamos uno mejor.

Según la idea de ire_and_curses, aquí está la solución en Java:

public int circularArraySearch(int[] a, int low, int high, int x){
    //instead of using the division op. (which surprisingly fails on big numbers)
    //we will use the unsigned right shift to get the average
    int mid = (low + high) >>> 1;
    if(a[mid] == x){
        return mid;
    }
    //a variable to indicate which half is sorted
    //1 for left, 2 for right
    int sortedHalf = 0;
    if(a[low] <= a[mid]){
        //the left half is sorted
        sortedHalf = 1;
        if(x <= a[mid] && x >= a[low]){
            //the element is in this half
            return binarySearch(a, low, mid, x);
        }
    }
    if(a[mid] <= a[high]){
        //the right half is sorted
        sortedHalf = 2;
        if(x >= a[mid] && x<= a[high] ){
            return binarySearch(a, mid, high, x);
        }
    }
    // repeat the process on the unsorted half
    if(sortedHalf == 1){
        //left is sorted, repeat the process on the right one
        return circularArraySearch(a, mid, high, x);
    }else{
        //right is sorted, repeat the process on the left
        return circularArraySearch(a, low, mid, x);
    }
}

Esperemos que esto funcione.

Answer 1

A continuación se muestra una implementación en C utilizando la búsqueda binaria.

int rotated_sorted_array_search(int arr[], int low, int high, int target)
{
    while(low<=high)
    {
        int mid = (low+high)/2;

        if(target == arr[mid])
            return mid;

        if(arr[low] <= arr[mid])
        {
            if(arr[low]<=target && target < arr[mid])
            {
                high = mid-1;
            }
            else
                low = mid+1;
        }
        else
        {
            if(arr[mid]< target && target <=arr[high])
            {
                low = mid+1;
            }
            else
                high = mid-1;
        }
    }
    return -1;
}

Answer 2

Aquí hay una idea, relacionada con la búsqueda binaria. Simplemente haga una copia de seguridad de su índice para el límite del índice de matriz derecho, el límite del índice izquierdo se almacena en el tamaño del paso:

step = n
pos = n
while( step > 0 ):
    test_idx = pos - step   #back up your current position
    if arr[test_idx-1] < arr[pos-1]:
        pos = test_idx
    if (pos == 1) break
    step /= 2 #floor integer division
return arr[pos]

Para evitar la cosa (pos == 1), podríamos hacer una copia de seguridad circular (ir a números negativos) y tomar (pos-1) mod n.

Answer 3

Aquí hay una solución en javascript. Lo probé con algunos arreglos diferentes y parece funcionar. Básicamente usa el mismo método descrito por ire_and_curses:

function search(array, query, left, right) {
  if (left > right) {
    return -1;
  }

  var midpoint = Math.floor((left + right) / 2);
  var val = array[midpoint];
  if(val == query) {
    return midpoint;
  }

  // Look in left half if it is sorted and value is in that 
  // range, or if right side is sorted and it isn''t in that range.
  if((array[left] < array[midpoint] && query >= array[left] && query <= array[midpoint])
    || (array[midpoint] < array[right] 
        && !(query >= array[midpoint] && query <= array[right]))) {
    return search(array, query, left, midpoint - 1);
  } else {
    return search(array, query, midpoint + 1, right);
  }
}

Answer 4

Aunque la respuesta aprobada es óptima, también podemos hacerlo con un algoritmo similar y más limpio.

1. ejecuta una búsqueda binaria para encontrar el elemento de pivote (donde se gira la matriz). O(logn)
2. la mitad izquierda del pivote se ordenará en orden decreciente, ejecute aquí una búsqueda binaria hacia atrás para la clave. O(logn)
3. la mitad derecha del pivote se ordenará en orden creciente, ejecute una búsqueda binaria hacia adelante en esta mitad para la clave. O(logn)
4. devuelva el índice de claves encontradas de los pasos 2 y 3.

Complejidad de tiempo total: O(logn)

Pensamientos bienvenidos.

Answer 5

Compruebe esto coe,

    def findkey():
    key = 3

    A=[10,11,12,13,14,1,2,3]
    l=0
    h=len(A)-1
    while True:
        mid = l + (h-l)/2
        if A[mid] == key:
            return mid
        if A[l] == key:
            return l
        if A[h] == key:
            return h
        if A[l] < A[mid]:
            if key < A[mid] and key > A[l]:
                h = mid - 1
            else:
                l = mid + 1
        elif A[mid] < A[h]:
            if key > A[mid] and key < A[h]:
                l = mid + 1
            else:
                h = mid - 1

if __name__ == ''__main__'':
    print findkey()

Answer 6

Creo que puedes encontrar el offset usando este código:

public static int findOffset(int [] arr){
        return findOffset(arr,0,arr.length-1);
    }
private static int findOffset(int[] arr, int start, int end) {

    if(arr[start]<arr[end]){
        return -1;
    }
    if(end-start==1){
        return end;
    }
    int mid = start + ((end-start)/2);
    if(arr[mid]<arr[start]){
        return findOffset(arr,start,mid);
    }else return findOffset(arr,mid,end);
}

Answer 7

Este es un ejemplo que funciona en Java. Dado que se trata de una matriz ordenada, aproveche esto y ejecute una búsqueda binaria, sin embargo, debe modificarse ligeramente para adaptarse a la posición del pivote.

El método se ve así:

private static int circularBinSearch ( int key, int low, int high )
{
    if (low > high)
    {
        return -1; // not found
    }

    int mid = (low + high) / 2;
    steps++;

    if (A[mid] == key)
    {
        return mid;
    }
    else if (key < A[mid])
    {
        return ((A[low] <= A[mid]) && (A[low] > key)) ?
               circularBinSearch(key, mid + 1, high) :
               circularBinSearch(key, low, mid - 1);
    }
    else // key > A[mid]
    {
        return ((A[mid] <= A[high]) && (key > A[high])) ?
               circularBinSearch(key, low, mid - 1) :
               circularBinSearch(key, mid + 1, high);
    }
}

Ahora para aliviar cualquier preocupación, aquí hay una pequeña clase que verifica el algoritmo:

public class CircularSortedArray
{
    public static final int[] A = {23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 
                                   91, 99, 1, 4, 11, 14, 15, 17, 19};
    static int steps;

    // ---- Private methods ------------------------------------------

    private static int circularBinSearch ( int key, int low, int high )
    {
        ... copy from above ...
    }

    private static void find ( int key )
    {
        steps = 0;
        int index = circularBinSearch(key, 0, A.length-1);
        System.out.printf("key %4d found at index %2d in %d steps/n",
                          key, index, steps);
    }

    // ---- Static main -----------------------------------------------

    public static void main ( String[] args )
    {
        System.out.println("A = " + Arrays.toString(A));
        find(44);   // should not be found
        find(230);
        find(-123);

        for (int key: A)  // should be found at pos 0..18
        {
            find(key);
        }
    }
}

Eso te da una salida de:

A = [23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 91, 99, 1, 4, 11, 14, 15, 17, 19]
key   44 found at index -1 in 4 steps
key  230 found at index -1 in 4 steps
key -123 found at index -1 in 5 steps
key   23 found at index  0 in 4 steps
key   27 found at index  1 in 3 steps
key   29 found at index  2 in 4 steps
key   31 found at index  3 in 5 steps
key   37 found at index  4 in 2 steps
key   43 found at index  5 in 4 steps
key   49 found at index  6 in 3 steps
key   56 found at index  7 in 4 steps
key   64 found at index  8 in 5 steps
key   78 found at index  9 in 1 steps
key   91 found at index 10 in 4 steps
key   99 found at index 11 in 3 steps
key    1 found at index 12 in 4 steps
key    4 found at index 13 in 5 steps
key   11 found at index 14 in 2 steps
key   14 found at index 15 in 4 steps
key   15 found at index 16 in 3 steps
key   17 found at index 17 in 4 steps
key   19 found at index 18 in 5 steps

Answer 8

No es muy elegante, pero sí de la parte superior de mi cabeza: solo use la búsqueda binaria para encontrar el pivote de la matriz rotada, y luego realice la búsqueda binaria nuevamente, compensando el desplazamiento del pivote. Es un poco tonto realizar dos búsquedas completas, pero cumple la condición, ya que O (log n) + O (log n) == O (log n). ¡Mantenlo simple y estúpido (tm)!

Answer 9

Puede hacerlo aprovechando el hecho de que la matriz está ordenada, excepto en el caso especial del valor pivote y uno de sus vecinos.

• Encuentra el valor medio de la matriz a.
• Si a[0] < a[mid] , se ordenan todos los valores en la primera mitad de la matriz.
• Si a[mid] < a[last] , entonces se ordenan todos los valores en la segunda mitad de la matriz.
• Tome la mitad ordenada y verifique si su valor se encuentra dentro de ella (compare con el IDx máximo en esa mitad).
• Si es así, solo binario busca esa mitad.
• Si no lo hace, debe estar en la mitad sin clasificar. Toma esa mitad y repite este proceso, determinando qué mitad de esa mitad está ordenada, etc.

Answer 10

Puede usar la búsqueda binaria para encontrar la ubicación del elemento más pequeño y reducirlo a O (Log n) .

Puede encontrar la ubicación por (esto es solo un esbozo de algoritmo, es inexacto pero puede obtener la idea):
1. i <- 1
2. j <- n
3. mientras yo <j
3.1. k <- (ji) / 2
3.2. si arr [k] <arr [i] entonces j <- k 3.3. si no <- k

Después de encontrar la ubicación del elemento más pequeño, puede tratar la matriz como dos matrices ordenadas.

Answer 11

Sencilla búsqueda binaria con un pequeño cambio.

Índice de matriz giratoria = (i + pivot)% tamaño

el pivote es el índice i + 1 donde a [i]> a [i + 1].

#include <stdio.h>
#define size 5
#define k 3
#define value 13
int binary_search(int l,int h,int arr[]){

int mid=(l+h)/2;

if(arr[(mid+k)%size]==value)
    return (mid+k)%size;

if(arr[(mid+k)%size]<value)
    binary_search(mid+1,h,arr);
else
    binary_search(l,mid,arr);
}

int main() {
    int arr[]={5,9,13,1,3};
    printf("found at: %d/n", binary_search(0,4,arr));
    return 0;
}

Answer 12

Simplemente utiliza una búsqueda binaria simple como si fuera una matriz ordenada regular. El único truco es que necesitas rotar los índices de matriz:

(index + start-index) mod array-size

donde el índice de inicio es el desplazamiento del primer elemento en la matriz circular.

Answer 13

Tiene tres valores, l , m , h para los valores en los índices bajo, medio y alto de su búsqueda. Si crees que seguirías buscando por cada posibilidad:

// normal binary search
l < t < m    - search(t,l,m)
m < t < h    - search(t,m,h)

// search over a boundary
l > m, t < m - search(t,l,m)
l > m, t > l - search(t,l,m)
m > h, t > m - search(t,m,h)  
m > h, t < h - search(t,m,h)  

Se trata de considerar dónde podría estar el valor objetivo y buscar esa mitad del espacio. A lo sumo, la mitad del espacio tendrá la envoltura, y es fácil determinar si el valor objetivo está en esa mitad o en la otra.

Es una especie de meta pregunta: ¿piensa en una búsqueda binaria en términos de cómo se presenta a menudo? Encontrar un valor entre dos puntos, o más generalmente como una división repetida de un espacio de búsqueda abstracta.

Answer 14

Un método simple en Ruby

def CircularArraySearch(a, x)
  low = 0
  high = (a.size) -1

  while low <= high
    mid = (low+high)/2
    if a[mid] == x
      return mid
    end
    if a[mid] <= a[high]
      if (x > a[mid]) && (x <= a[high])
        low = mid + 1
      elsif high = mid -1
      end
    else
      if (a[low] <= x) && (x < a[mid])
        high = mid -1
      else
        low = mid +1
      end
    end
  end
  return -1
end

a = [12, 14, 18, 2, 3, 6, 8, 9]
x = gets.to_i
p CircularArraySearch(a, x)

Answer 15

guirgis: es un error publicar una pregunta de entrevista, supongo que no obtuviste el trabajo :-(

Use una función especial de cmp y solo necesita un pase con la búsqueda binaria regular. Algo como:

def rotatedcmp(x, y):
  if x and y < a[0]:
    return cmp(x, y)
  elif x and y >= a[0]:
    return cmp(x, y)
  elif x < a[0]:
    return x is greater
  else:
    return y is greater

Si puede depender de un subflujo int, reste un [0] - MIN_INT de cada elemento a medida que se accede y use la comparación regular.

Answer 16

public static int _search(int[] buff, int query){
    int s = 0;
    int e = buff.length;
    int m = 0; 

    while(e-s>1){
        m = (s+e)/2;
        if(buff[offset(m)] == query){
            return offset(m);
        } else if(query < buff[offset(m)]){
            e = m;
        } else{
            s = m;
        }
    }

    if(buff[offset(end)]==query) return end;
    if(buff[offset(start)]==query) return start;
    return -1;
}

public static int offset(int j){
    return (dip+j) % N;
}