Recherche d'un élément dans un tableau avec une complexité meilleure que O(n)

Question

Je dispose d'un tableau dont les éléments sont d'abord classés par ordre croissant, puis par ordre décroissant.

Comme A[10]={1,4,6,8,3,2} , sans doublon dans un tableau.

si l'entrée est 7, la sortie devrait être, l'élément n'existe pas.

La complexité temporelle devrait être meilleure que O(n)

J'obtiens le résultat par la recherche linéaire, en comparant chaque élément avec l'élément à trouver. Mais comme je veux une solution meilleure que O(n)

J'ai essayé de trouver un pivot où l'élément du tableau se retourne, puis de chercher à partir de (0 à l'élément pivot) et ensuite de chercher à nouveau dans (dernier élément à l'élément pivot).

Veuillez nous suggérer. Pour O(n)

 #include<iostream>
 int main()
 {
     int A[10]={1,4,6,8,3,2};
     int i,num
     cout<<"Enter the element to be searched";
     cin>>num
     for(i=0;i<10;i++)
     {
         If(A[i]==num)
        {
          cout<<"Element exist";
         break;
      }
         else
         cout<<"Element do not exist";
     }
 }

Answer 1

Algorithme :

1. Trouver max dans log(n) en effectuant une recherche binaire et enregistrer son index.
2. Effectuer une recherche binaire sur les deux côtés de max.
3. S'il n'est pas trouvé et que l'élément n'est pas égal au maximum, il n'existe pas.

Comment procéder à l'étape 1 ?

• choisir le milieu du tableau
• vérifiez-le par rapport à l'élément de gauche (votre voisin). S'il est plus grand, le maximum se trouve du côté droit. Sinon, nous avons commencé par la séquence décroissante et le maximum se trouve à gauche. La façon de choisir s'il faut chercher à droite ou à gauche dépend du fait que l'élément de gauche est plus grand ou plus petit.

EDIT
Au cas où ce ne serait pas clair : si l'on choisit n/2e élément et qu'il s'avère que le maximum est à gauche, on choisit alors n/4e élément, si le maximum est à droite, on ne poursuit la recherche que dans l'intervalle n/4...n/2 éléments.