Moyen efficace de trouver le nombre maximum dans un tableau

Dans ce cas, tout ce que vous avez à faire est de déterminer si c’est (3). Sinon, la réponse est max (premier, dernier).

Dans le cas où tous les éléments sont égaux, vous devrez effectuer une recherche exhaustive dans le tableau pour montrer qu’il n’y a pas un nombre élevé quelque part au milieu. Donc, je pense que c’est O (n) pour déterminer si vous êtes dans (3).

Eh bien, au cas par cas, vous avez

1. Le dernier numéro.
2. Le premier numéro
3. Déplacez-vous du début à la fin, en vous arrêtant à la première descente et en imprimant le numéro précédent.
4. Comparez les premier et dernier chiffres.

Si vous ne savez pas dans quel cas vous vous trouvez, vous pouvez le tester tout en trouvant le maximum en procédant comme suit (en pseudocode de type C):

 for (int i=0; i array[j+1]) { // CASE 3 return array[j]; } } // CASE 1 return array[end]; } } // CASE 2 or 4 return max(array[0],array[end]); 

Vous pourrez déterminer avec le type de tableau que c’est en inspectant les deux premiers et les deux derniers

1. C’est le dernier élément
2. C’est le premier élément
3. voir ci-dessous
4. C’est le plus grand des premier et dernier éléments

Pour 3, commençons par examiner deux éléments au milieu du tableau. S’ils augmentent toujours, le maximum est plus élevé dans le tableau. S’ils diminuent, le maximum est plus bas dans le tableau. Répéter de manière binary

Etant donné que les cas 1-3 ont tous un pic (valeur entourée des deux côtés par des valeurs plus basses que lui-même ou le bord du tableau) et que le cas 4 a deux pics aux deux extrémités du tableau, ce problème peut être résolu assez simplement Temps O(log n) pour tous les cas:

Tout d’abord, appliquez l’algorithme de recherche de pic 1D pour rechercher un pic dans la masortingce.

Si le pic se situe au milieu du tableau (et non la première ou la dernière position), il s’agit du cas n ° 3 et le pic est également le maximum.

Si le pic correspond au premier ou au dernier élément du tableau, il s’agit alors de l’un des cas 1, 2 ou 4 et le tableau max est max (premier, dernier).

Pseudo-code Python-esque:

 def find-peak(list): mid=len(list)/2 if (list[mid-1] > list[mid]: return find-peak(list[:mid-1]) else if (list[mid+1] > list[mid]: return find-peak(list[mid+1:]) else: return mid def find-max(list): peak = find-peak(list) if peak==0 or peak==len(list)-1: return max(list[0], list[-1]) else: return list[peak] 

1.le dernier numéro 2.le premier numéro 3.fait une recherche de type binary, choisissez un pivot, calculez la pente, juste pour décider ensuite d’aller à gauche ou à droite 4. premier ou dernier numéro

Le moyen d’identifier les quatre cas est simple si nous supposons que la séquence n’a pas de numéro répétitif:

 case 1: arr[0] < arr[1] && arr[end-1] < arr[end] case 2: arr[0] > arr[1] && arr[end-1] > arr[end] case 3: arr[0] < arr[1] && arr[end-1] > arr[end] case 4: arr[0] > arr[1] && arr[end-1] < arr[end] 

Comme mentionné dans d'autres réponses, la manière de trouver le max est également simple:

 case 1: arr[end] case 2: arr[0] case 3: binary search, until found n that arr[n-1] < arr[n] > arr[n+1] case 4: max(arr[0],arr[end]) 

La réponse dépend de ce que l’on entend par “efficacité”. Si vous voulez un code rapide, regardez la réponse de quelqu’un d’autre. Si vous voulez être efficace en tant que programmeur, vous devriez probablement simplement utiliser un appel de bibliothèque (comme max_element() en C ++).

Ce problème me rappelle l’ algorithme de la section d’or pour trouver le minimum d’une fonction unimodulaire (c’est-à-dire décroissante puis croissante). C’est en quelque sorte une version améliorée de la recherche binary qui calcule la valeur de la fonction (c’est-à-dire: inspecte le tableau) en aussi peu de points que possible.

Il ne vous rest plus qu’à le traduire en une version discrète et à append des sifflets supplémentaires pour déterminer si la fonction est concave ou convexe.