Binaire de recherche pour trouver le point de rotation dans une zone de liste triée

Une légère modification sur le binaire de l'algorithme de recherche est tout ce dont vous avez besoin; voici la solution complète exécutable Java (voir Serg réponse pour Delphi mise en œuvre, et atg réponse pour une explication visuelle de l'algorithme).

import java.util.*;
public class BinarySearch {
    static int findMinimum(Integer[] arr) {
        int low = 0;
        int high = arr.length - 1;
        while (arr[low] > arr[high]) {
            int mid = (low + high) >>> 1;
            if (arr[mid] > arr[high]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    public static void main(String[] args) {
        Integer[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        //must be in sorted order, allowing rotation, and contain no duplicates

        for (int i = 0; i < arr.length; i++) {
            System.out.print(Arrays.toString(arr));
            int minIndex = findMinimum(arr);
            System.out.println(" Min is " + arr[minIndex] + " at " + minIndex);
            Collections.rotate(Arrays.asList(arr), 1);
        }
    }
}

Cette affiche:

[1, 2, 3, 4, 5, 6, 7] Min is 1 at 0
[7, 1, 2, 3, 4, 5, 6] Min is 1 at 1
[6, 7, 1, 2, 3, 4, 5] Min is 1 at 2
[5, 6, 7, 1, 2, 3, 4] Min is 1 at 3
[4, 5, 6, 7, 1, 2, 3] Min is 1 at 4
[3, 4, 5, 6, 7, 1, 2] Min is 1 at 5
[2, 3, 4, 5, 6, 7, 1] Min is 1 at 6

Voir aussi

• Java Collections.rotate() avec un tableau ne fonctionne pas
  • Explique pourquoi Integer[] au lieu de int[]
• Google Blog de Recherche: Près de Tous les Binaires de Recherches et Mergesorts sont Cassés
  • Explique pourquoi >>> 1 au lieu de /2

---

Sur les doublons

Noter que les doublons fait qu'il est impossible de le faire dans O(log N). Considérez les points suivants tableau de bits composé de nombreux 1, et un 0:

  (sorted)
  01111111111111111111111111111111111111111111111111111111111111111
  ^

  (rotated)
  11111111111111111111111111111111111111111111101111111111111111111
                                               ^

  (rotated)
  11111111111111101111111111111111111111111111111111111111111111111
                 ^

Ce tableau peut être mis en rotation dans N façons, et la localisation de l' 0 dans O(log N) est impossible, car il n'y a aucun moyen de savoir si c'est dans le côté gauche ou droit de le "milieu".

---

J'ai une autre condition. Que faire si la liste n'est pas triée??

Alors, à moins que vous voulez trier d'abord et procéder à partir de là, vous devrez faire un linéaire de recherche pour trouver le minimum.

Voir aussi

• Wikipedia | algorithme de Sélection | Linéaire minimum/maximum algorithmes

Je voudrais faire une recherche binaire sur la liste pour trouver le minimum de l'élément.

Ternaire, de recherche de travail pour ce cas: lorsque la fonction a exactement un minimum local.

http://en.wikipedia.org/wiki/Ternary_search

modifier
Lors de la deuxième lecture, j'ai probablement mal compris la question: la fonction n'est pas conforme exigences pour le ternaire de recherche :/Mais qui ne sont pas binaires de recherche de travail? Supposons, par ordre d'origine était en augmentation.

if (f(left) < f(middle)) 
    //which means, 'left' and 'middle' are on the same segment (before or after point X we search)
    //and also 'left' is before X by definition
    //so, X must be to the right from 'middle'
    left = middle
else
    right = middle

Delphi version du tiers amélioré (grâce à polygenelubricants code - encore un de plus la comparaison supprimé) variante:

type
  TIntegerArray = array of Integer;

function MinSearch(A: TIntegerArray): Integer;
var
  I, L, H: Integer;

begin
  L:= Low(A);   //= 0
  H:= High(A);  //= Length(A) - 1
  while A[L] > A[H] do begin
    I:= (L + H) div 2; //or (L + H) shr 1 to optimize
    Assert(I < H);
    if (A[I] > A[H])
      then L:= I + 1
      else H:= I;
  end;
  Result:= A[L];
end;

Ma version binaire de l'algorithme de recherche mise en œuvre dans Java:

/**
 * Works only for arrays with NO duplicates.
 * Work also for zero-shifted array, e.g fully sorted, when shift = 0.
 */
public static int searchInShiftedArr(int[] arr, int key) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int low = 0;
    int high = arr.length - 1;
    int mid; //declared outside loop to avoid constant memory allocation for this variable
    while (low <= high) {
        mid = (low + high) >>> 1; //same as "(low + high) /2", but avoid negative overflow and should be faster than "low + (high - low)/2"
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[low] <= arr[mid]) { //means left half of the array is sorted
            if (arr[low] <= key && key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else { //means right half of the array is sorted
            if (arr[mid] < key && key <= arr[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

Code passé avec succès 5000 cas de tests, donc je pense qu'il est prêt pour la production.

Quelque chose comme ça pourrait fonctionner (Pas testé):

//assumes the list is a std::vector<int> myList

int FindMinFromRotated(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
    if (begin == end)
        throw std::invalid_argument("Iterator range is singular!");
    if (std::distance(begin, end) == 1) //What's the min of one element?
        return *begin;
    if (*begin < *end) //List is sorted if this is true.
        return *begin;
    std::vector<int>::iterator middle(begin);
    std::advance(middle, std::distance(begin, end)/2);
    if (*middle < *begin) //If this is true, than the middle element selected is past the rotation point
        return FindMinFromRotated(begin, middle)
    else if (*middle > *begin) //If this is true, the the middle element selected is in front of the rotation point.
        return FindMinFromRotated(middle, end)
    else //Looks like we found what we need :)
        return *begin;
}