algorithm - una - hallar incognitas en matrices

Dada una matriz bitónica y un elemento x en la matriz, encuentre el índice de x en tiempo 2log(n)

Question

Primero, una matriz bitónica para esta pregunta se define como una tal que para algún índice K en una matriz de longitud N donde 0 < K < N - 1 y 0 a K es una secuencia de números enteros que aumenta monotónicamente y K a N - 1 Es una secuencia monotónica decreciente de enteros.

Ejemplo: [1, 3, 4, 6, 9, 14, 11, 7, 2, -4, -9] . Aumenta monótonamente de 1 a 14, luego disminuye de 14 a -9.

El precursor de esta pregunta es resolverlo en 3log(n) , que es mucho más fácil. Una búsqueda binaria modificada para encontrar el índice del máximo, luego dos búsquedas binarias de 0 a K y K + 1 a N - 1 respectivamente.

Supongo que la solución en 2log(n) requiere que resuelva el problema sin encontrar el índice del máximo. He pensado en superponer las búsquedas binarias, pero más allá de eso, no estoy seguro de cómo avanzar.

Answer 1

El algoritmo funciona recursivamente al combinar búsquedas bitónicas y binarias:

def bitonic_search (array, value, lo = 0, hi = array.length - 1)
if array[lo] == value then return lo
if array[hi] == value then return hi
mid = (hi + lo) / 2
if array[mid] == value then return mid
if (mid > 0 & array[mid-1] < array[mid])
| (mid < array.length-1 & array[mid+1] > array[mid]) then
# max is to the right of mid
bin = binary_search(array, value, low, mid-1)
if bin != -1 then return bin
return bitonic_search(array, value, mid+1, hi)
else # max is to the left of mid
bin = binary_search(array, value, mid+1, hi)
if bin != -1 then return bin
return bitonic_search(array, value, lo, mid-1)

Entonces, la fórmula recursiva para el tiempo es f(l) = f(l/2) + log(l/2) + c donde log(l/2) proviene de la búsqueda binaria y c es el costo de las comparaciones realizadas en El cuerpo de la función.

Answer 2

Encontrar el cambio de signo entre las diferencias de primer orden, mediante la búsqueda dicotómica estándar, tomará 2Lg(n) arreglos de acceso.

Puede hacerlo un poco mejor usando la estrategia de búsqueda para el máximo de una función unimodal conocida como búsqueda de Fibonacci. Después de n pasos, cada uno de los cuales involucra una sola búsqueda, reduce el tamaño del intervalo en un factor Fn , correspondiente a aproximadamente Log n/Log φ ~ 1.44Lg(n) accesos para encontrar el máximo.

Esta ganancia marginal tiene un poco más de sentido cuando los accesos de matrices son evaluaciones de funciones costosas.

Answer 3

Hay 5 casos principales dependiendo de dónde está el elemento max de la matriz y si el elemento del medio es mayor que el valor deseado

Calcular elemento medio. Compare el valor deseado del elemento intermedio, si coincide con los fines de búsqueda. De lo contrario, proceda al siguiente paso.

1. Compare el elemento central con los vecinos para ver si el elemento máximo está a la izquierda o a la derecha. Si los dos vecinos son menos que el elemento medio, entonces el elemento no está presente en la matriz, por lo tanto sale (la matriz mencionada en la pregunta llegará a este caso primero como 14, el elemento max, está en la mitad)

2. Si el elemento central es menor que el valor deseado y el elemento máximo está a la derecha, haga una búsqueda bitónica en el subarreglo derecho

3. Si el elemento medio es menor que el valor deseado y el elemento máximo está a la izquierda, haga una búsqueda bitónica en el subarreglo izquierdo

4. Si el elemento central es mayor que el valor deseado y el elemento máximo está a la izquierda, haga una búsqueda binaria descendente en el subarreglo derecho

5. Si el elemento central es mayor que el valor deseado y el elemento máximo está a la derecha, realice una búsqueda binaria ascendente en el subarreglo izquierdo

En el peor de los casos, haremos dos comparaciones cada vez que la matriz se divide por la mitad, por lo que la complejidad será 2 * logN

Answer 4

Las respuestas proporcionadas tienen una complejidad de tiempo de (N / 2) * logN. Porque el peor de los casos puede incluir demasiadas búsquedas secundarias que son innecesarias. Una modificación es comparar el valor objetivo con el elemento izquierdo y derecho de la subserie antes de buscar. Si el valor objetivo no se encuentra entre dos extremos de la serie monotónica o menor que ambos extremos de la serie bitónica, la búsqueda subsiguiente es redundante. Esta modificación lleva a 2lgN de complejidad.

Answer 5

Para una división binaria, hay tres casos:

1. el elemento máximo está a la derecha, luego la búsqueda binaria a la izquierda y la búsqueda a la derecha.
2. el elemento máximo está a la izquierda, luego la búsqueda binaria a la derecha y la búsqueda a la izquierda.
3. El elemento máximo se encuentra exactamente en el punto de división, luego binario tanto a la izquierda como a la derecha.

precaución: la búsqueda binaria utilizada en la izquierda y la derecha son diferentes debido a un orden creciente / decreciente.

public static int bitonicSearch(int[] a, int lo, int hi, int key) {
int mid = (lo + hi) / 2;
int now = a[mid];
if (now == key)
return mid;
// deal with edge cases
int left = (mid == 0)? a[mid] : a[mid - 1];
int right = (mid == a.length-1)? a[mid] : a[mid + 1];
int leftResult, rightResult;
if (left < now && now < right) { // max item is at right
leftResult = binarySearchIncreasing(a, lo, mid - 1, key);
if (leftResult != -1)
return leftResult;
return bitonicSearch(a, mid + 1, hi, key);
}
else if (left > now && now > right) { // max item is at left
rightResult = binarySearchDecreasing(a, mid + 1, hi, key);
if (rightResult != -1)
return rightResult;
return bitonicSearch(a, lo, mid - 1, key);
}
else { // max item stands at the split point exactly
leftResult = binarySearchIncreasing(a, lo, mid - 1, key);
if (leftResult != -1)
return leftResult;
return binarySearchDecreasing(a, mid + 1, hi, key);
}
}

Answer 6

Los algoritmos presentados en otras respuestas ( this y this ) son desafortunadamente incorrectos, ¡no son O (logN)!

La fórmula recursiva f (L) = f (L / 2) + log (L / 2) + c no conduce a f (L) = O (log (N)), pero lleva a f (L) = O ( (log (N)) ^ 2) !

De hecho, supongamos que k = log (L), luego log (2 ^ (k-1)) + log (2 ^ (k-2)) + ... + log (2 ^ 1) = log (2) * ( k-1 + k-2 + ... + 1) = O (k ^ 2). Por lo tanto, log (L / 2) + log (L / 4) + ... + log (2) = O ((log (L) ^ 2)).

La forma correcta de resolver el problema en el tiempo ~ 2log (N) es proceder de la siguiente manera (asumiendo que la matriz está primero en orden ascendente y luego en orden descendente):

1. Toma el centro de la matriz
2. Compara el elemento central con uno de sus vecinos para ver si el máximo está a la derecha o a la izquierda
3. Compara el elemento del medio con el valor deseado.
4. Si el elemento central es más pequeño que el valor deseado Y el máximo está en el lado izquierdo, entonces realice una búsqueda bitónica en el subarreglo izquierdo (estamos seguros de que el valor no está en el subarreglo derecho)
5. Si el elemento central es más pequeño que el valor deseado Y el máximo está en el lado derecho, haga una búsqueda bitónica en el subarreglo derecho
6. Si el elemento central es más grande que el valor deseado, realice una búsqueda binaria descendente en el subarreglo derecho y una búsqueda binaria ascendente en el subarreglo izquierdo.

En el último caso, puede ser sorprendente realizar una búsqueda binaria en un subarreglo que puede ser bitónico, pero en realidad funciona porque sabemos que los elementos que no están en el orden correcto son todos más grandes que el valor deseado. Por ejemplo, hacer una búsqueda binaria ascendente para el valor 5 en la matriz [2, 4, 5, 6, 9, 8, 7] funcionará porque 7 y 8 son más grandes que el valor deseado 5.

Aquí hay una implementación completamente funcional (en C ++) de la búsqueda bitónica en el tiempo ~ 2logN :

#include <iostream>
using namespace std;
const int N = 10;
void descending_binary_search(int (&array) [N], int left, int right, int value)
{
// cout << "descending_binary_search: " << left << " " << right << endl;
// empty interval
if (left == right) {
return;
}
// look at the middle of the interval
int mid = (right+left)/2;
if (array[mid] == value) {
cout << "value found" << endl;
return;
}
// interval is not splittable
if (left+1 == right) {
return;
}
if (value < array[mid]) {
descending_binary_search(array, mid+1, right, value);
}
else {
descending_binary_search(array, left, mid, value);
}
}
void ascending_binary_search(int (&array) [N], int left, int right, int value)
{
// cout << "ascending_binary_search: " << left << " " << right << endl;
// empty interval
if (left == right) {
return;
}
// look at the middle of the interval
int mid = (right+left)/2;
if (array[mid] == value) {
cout << "value found" << endl;
return;
}
// interval is not splittable
if (left+1 == right) {
return;
}
if (value > array[mid]) {
ascending_binary_search(array, mid+1, right, value);
}
else {
ascending_binary_search(array, left, mid, value);
}
}
void bitonic_search(int (&array) [N], int left, int right, int value)
{
// cout << "bitonic_search: " << left << " " << right << endl;
// empty interval
if (left == right) {
return;
}
int mid = (right+left)/2;
if (array[mid] == value) {
cout << "value found" << endl;
return;
}
// not splittable interval
if (left+1 == right) {
return;
}
if(array[mid] > array[mid-1]) {
if (value > array[mid]) {
return bitonic_search(array, mid+1, right, value);
}
else {
ascending_binary_search(array, left, mid, value);
descending_binary_search(array, mid+1, right, value);
}
}
else {
if (value > array[mid]) {
bitonic_search(array, left, mid, value);
}
else {
ascending_binary_search(array, left, mid, value);
descending_binary_search(array, mid+1, right, value);
}
}
}
int main()
{
int array[N] = {2, 3, 5, 7, 9, 11, 13, 4, 1, 0};
int value = 4;
int left = 0;
int right = N;
// print "value found" is the desired value is in the bitonic array
bitonic_search(array, left, right, value);
return 0;
}

Answer 7

 public int FindLogarithmicGood(int value)
{
int lo = 0;
int hi = _bitonic.Length - 1;
int mid;
while (hi - lo > 1)
{
mid = lo + ((hi - lo) / 2);
if (value < _bitonic[mid])
{
return DownSearch(lo, hi - lo + 1, mid, value);
}
else
{
if (_bitonic[mid] < _bitonic[mid + 1])
lo = mid;
else
hi = mid;
}
}
return _bitonic[hi] == value
? hi
: _bitonic[lo] == value
? lo
: -1;
}

donde DownSearch es

 public int DownSearch(int index, int count, int mid, int value)
{
int result = BinarySearch(index, mid - index, value);
if (result < 0)
result = BinarySearch(mid, index + count - mid, value, false);
return result;
}

y BinarySearch es

 /// <summary>
/// Exactly log(n) on average and worst cases.
/// Note: System.Array.BinarySerch uses 2*log(n) in the worst case.
/// </summary>
/// <returns>array index</returns>
public int BinarySearch(int index, int count, int value, bool asc = true)
{
if (index < 0 || count < 0)
throw new ArgumentOutOfRangeException();
if (_bitonic.Length < index + count)
throw new ArgumentException();
if (count == 0)
return -1;
// "lo minus one" trick
int lo = index - 1;
int hi = index + count - 1;
int mid;
while (hi - lo > 1)
{
mid = lo + ((hi - lo) / 2);
if ((asc && _bitonic[mid] < value) || (!asc && _bitonic[mid] > value))
lo = mid;
else
hi = mid;
}
return _bitonic[hi] == value ? hi : -1;
}

github