Étant donné un bitonic tableau et de l'élément x dans le tableau, trouver l'indice de x dans 2log(n) le temps

Tout d'abord, un bitonic tableau pour cette question est définie comme un tel que, pour tout indice K dans un tableau de longueur N où 0 < K < N - 1 et de 0 à K est monotone croissante de la séquence de nombres entiers, et K à N - 1 est une façon monotone décroissante de la séquence de nombres entiers.

Exemple: [1, 3, 4, 6, 9, 14, 11, 7, 2, -4, -9]. Il augmente de façon monotone de 1 à 14 ans, puis diminue à partir de 14 à -9.

Le précurseur de cette question est de résoudre dans 3log(n), qui est beaucoup plus facile. Une altération de la recherche binaire pour trouver l'index de max, puis deux binaires des recherches de 0 à K et K + 1 à N - 1, respectivement.

Je suppose que la solution dans 2log(n) vous demande de résoudre le problème sans trouver de l'index max. J'ai pensé recouvrent les binaires de recherche, mais au-delà, je ne suis pas sûr de savoir comment aller de l'avant.

Je pense que plausible route est de faire deux binaires de recherche, en supposant que le milieu de l'élément est le max. Puis, dans les deux binaires de recherches que nous inclure une contrainte de regarder dehors pour une certaine incohérence, qui, à un certain point l'une des deux moitiés ne sont pas monotone croissante/décroissante. Une fois trouvée, la recherche binaire qui fait flac chacun sur ce s'ajuste en conséquence. La question ici serait ce que pour regarder dehors pour.
Toutefois, si le milieu n'était pas le max, il est possible que les deux binaires recherches convergent vers un seul côté, ce qui signifie que l'on serait redondant. Dans ce cas, nous devons forcer l'un des binaires de recherche l'autre sens jusqu'à ce qu'il fonctionne de lui-même et ne se déplace pas vers l'autre en binaire de recherche. Je pense que ce serait la façon d'aller à ce sujet.
Comment fonctionne la recherche pour le max de travail à exactement log n sans facteur constant de toute façon?
flexaired.blogspot.com/2013/06/...

OriginalL'auteur David | 2013-10-15

  1. 37

    Les algorithmes présentés dans les autres réponses (cette et cette) sont malheureusement incorrecte, ils ne sont pas en O(logN) !

    La formule récursive f(L) = f(L/2) + log(L/2) + c ne conduit pas à f(L) = O(log(N)), mais conduit à f(L) = O((log(N))^2) !

    En effet, supposons k = log(L), alors log(2^(k-1)) + log(2^(k-2)) + ... + log(2^1) = log(2)*(k-1 + k-2 + ... + 1) = O(k^2). Par conséquent, log(L/2) + log(L/4) + ... + log(2) = O((log(L)^2)).

    La bonne façon de résoudre le problème dans le temps ~ 2log(N) est de procéder comme suit (en supposant que le tableau est premier dans l'ordre croissant, puis dans l'ordre décroissant):

    1. Prendre le milieu de la collection
    2. Comparer le milieu de l'élément avec l'un de ses voisin, pour voir si le max est sur la droite ou sur la gauche
    3. Comparer le milieu de l'élément avec la valeur souhaitée
    4. Si le milieu de l'élément est plus petit que la valeur souhaitée ET le max est sur le côté gauche, puis faire bitonic de recherche sur la gauche subarray (nous sommes sûr que la valeur n'est pas dans la bonne subarray)
    5. Si le milieu de l'élément est plus petit que la valeur souhaitée ET le max est sur le côté droit, puis faire bitonic de recherche sur la droite subarray
    6. Si le milieu de l'élément est plus grand que la valeur souhaitée, puis l'ordre décroissant binaire de recherche sur la droite subarray et croissant binaire de recherche sur la gauche subarray.

    Dans le dernier cas, il peut être surprenant de faire une recherche binaire sur un subarray qui peuvent être bitonic mais il fonctionne réellement, car nous savons que les éléments qui ne sont pas dans le bon de commande sont tous plus grand que la valeur souhaitée. Par exemple, en faisant un croissant de recherche binaire pour la valeur 5 dans le tableau [2, 4, 5, 6, 9, 8, 7] va travailler parce que les 7 et 8 sont plus grandes que la valeur souhaitée 5.

    Ici est un travail entièrement mise en œuvre (en C++) de la bitonic de recherche dans le temps ~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;
}
    N' "dichotomic_search" ici signifie "recherche binaire"?
    absolument ! J'ai édité le post et a remplacé "dichotomic_search' par 'binary_search" pour être cohérent avec l'explication.
    Pouvez-vous expliquer votre relation de récurrence.
    L'hypothèse à la recherche binaire ne fonctionne pas? Dire que le tableau d'entiers [2, 4, 5, 6, 9, 8, 1] ?
    Un (personnalisé) binaire de recherche travaille aussi longtemps que les valeurs se répartissent autour cherché valeur.Nous avons en effet impossible d'utiliser un std (std::binary_search ou std::lower_bound) car il sera UB.

    OriginalL'auteur user3017842

  2. 2

    L'algorithme fonctionne de manière récursive en combinant bitonic et binaires de recherche:

    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)

    De sorte que la formule récursive pour le moment est f(l) = f(l/2) + log(l/2) + c où log(l/2) vient de la recherche binaire et c est le coût de la comparaison faite dans le corps de la fonction.

    Je suppose que la méthode est a commencé avec lo étant le premier élément et le salut étant le dernier élément?
    Je ne suis pas familier avec bitonic de recherche, donc, je dois demander: sont & et | opérations binaires ou une abréviation pour désigner && et ||?
    oui, ce sont les opérations logiques and et or (c'est pseudocode)

    OriginalL'auteur sds

  3. 1
        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;
    }

    où DownSearch est

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

    et BinarySearch est

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

    OriginalL'auteur Denis Larionov

  4. 1

    Trouver le changement de signe entre le premier ordre différences, par standard dichotomique de recherche, prendra 2Lg(n) accès à des tableaux.

    Vous pouvez faire un peu mieux à l'aide de la stratégie de recherche de la valeur maximale d'un unimodale fonction dite de Fibonacci de recherche. Après n étapes, chacune impliquant une seule recherche, vous réduisez l'intervalle de la taille par un facteur Fn, correspondant à environ Log n/Log φ ~ 1.44Lg(n) accède à trouver le maximum.

    Ce gain marginal fait un peu plus de sens lorsque l'accès à des tableaux sont plutôt coûteux d'une fonction d'évaluations.

    OriginalL'auteur Yves Daoust

  5. 0

    Réponses à celles fournies avoir le temps de la complexité de (N/2)*logN. Parce que le pire des cas, peut inclure trop de sous-recherches qui sont inutiles. Une modification est à comparer à la valeur cible à gauche et à droite de l'élément de la sous-série avant la recherche. Si la valeur cible n'est pas entre les deux extrémités de la monotone de la série ou du moins que les deux extrémités de la bitonic de la série, à la suite de la recherche est redondante. Cette modification conduit à 2lgN complexité.

    OriginalL'auteur Bravo

  6. 0

    Il y a 5 principaux cas selon l'endroit où le max élément du tableau est, et si le milieu de l'élément est supérieure à la valeur désirée

    Calculer milieu de l'élément.
    Comparer milieu de l'élément valeur désirée, si elle correspond à la recherche se termine. Sinon, passez à l'étape suivante.

    1. Comparer milieu de l'élément avec les voisins pour voir si max élément est sur la gauche ou la droite. Si les deux voisins sont à moins de moyen de l'élément, puis l'élément n'est pas présent dans la table, donc la sortie.(Tableau mentionné dans la question va frapper ce cas, d'abord comme 14, le max élément, est en moyenne)

    2. Si le milieu de l'élément est inférieure à la valeur désirée et max élément est sur la droite, ne bitonic de recherche en droit subarray

    3. Si le milieu de l'élément est inférieure à la valeur désirée et max élément est sur la gauche, ne bitonic de recherche à gauche subarray

    4. Si le milieu de l'élément est supérieure à la valeur désirée et max élément est sur la gauche, l'ordre décroissant binaire de recherche en droit subarray

    5. Si le milieu de l'élément est supérieure à la valeur désirée et max élément est sur la droite, ne croissant binaire de recherche à gauche subarray

    Dans le pire des cas, nous allons faire deux comparaisons à chaque fois tableau est divisé en deux, d'où la complexité sera de 2*logN

    OriginalL'auteur Manohar Bhat

  7. -1

    Un binaire split, il y a trois cas:

    1. max élément est à droite, le binaire de recherche à gauche, et bitoinc de recherche à droite.
    2. max élément est à gauche, le binaire de recherche droit et bitoinc de recherche à gauche.
    3. max élément est sur le point de split exactement, le binaire à la fois de gauche et de droite.

    attention: la recherche binaire utilisé à gauche et à droite sont différentes en raison de l'augmentation/la diminution de l'ordre.

    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);
    }
}
    max item stands at the split point exactly trompeuse commentaire

    OriginalL'auteur Dongliang Yu