Critères de recherche optimaux dans ce tableau ?

Question

Je viens de passer cet examen, dans lequel il y avait une question : Considérons un tableau de taille 2n, où les nombres en position impaire sont triés par ordre croissant et les nombres en position paire par ordre décroissant. Maintenant, si je dois rechercher un nombre dans ce tableau, quelle est la bonne façon de le faire ? Les options sont les suivantes :

1. Tri rapide et ensuite recherche binaire
2. Fusionner les deux tableaux triés, puis effectuer une recherche binaire.
3. Recherche séquentielle

En 1, le tri rapide prend O(n log n) et la recherche binaire, O(log n).

En 2, la fusion prend O(n) et ensuite O(log n) pour la recherche binaire.

En 3, cela prend O(n).

Donc 3 s'avère être le chemin à suivre. Est-ce correct ? Existe-t-il un meilleur choix qui n'aurait pas été donné ?

EDIT : J'ai accepté la réponse de Lukas puisqu'il était le premier. Soupir, que était l'autre option. J'obtiens un -1. :(

Answer 1

Vous pouvez effectuer deux recherches binaires - c'est O(log n), car vous ignorez les constantes (2 dans ce cas).

Answer 2

Ne serait-il pas plus simple d'effectuer une recherche binaire sur les deux ensembles ? Donc O(log n) et O(log n) ?

Ne serait-il pas plus simple de faire en sorte que, si l'on trouve la première, la deuxième étape ne soit même pas nécessaire ?

Answer 3

Vérifiez s'il est pair ou impair, et faites une recherche binaire sur la partie du tableau qui vous intéresse. O(log n).

Answer 4

Je pense que la deuxième option correspond à vos critères.

Triage par fusion : Nous pouvons facilement obtenir un tableau complet de nombres triés à partir de deux tableaux à moitié triés avec une complexité temporelle de O(n).

Et alors la recherche binaire aura une complexité en temps de O(logn)