Recherche binaire d'un tableau trié

Il y a une recherche binaire dans le Array classe:

int index = Array.BinarySearch(mynumbers, target);

Pour l'ordre décroissant, cela peut être facilement accompli avec un ReverseComparer qui est facile à écrire comme:

    public class ReverseComparer<T> : IComparer<T>
    {
        public int Compare(T x, T y)
        {
            return Comparer<T>.Default.Compare(y, x);
        }
    }

Alors:

int index = Array.BinarySearch(numbers, 7, new ReverseComparer<int>());

Si c'est un exercice académique et vous devez utiliser une recherche personnalisée, bien sûr, il ne sera pas appliqué. Si il faut un algorithme personnalisé pour une classe, alors le problème est que vous devez sortir de la boucle quand on les trouve, et l'index est à mid, pas à mynumbers[mid]:

    //for a sorted array with descending values
    while (first<=last)
    {
        mid = (first + last) / 2;

        if (target < mynumbers[mid])
        {
            first = mid + 1;
        }

        if (target > mynumbers[mid])
        {
            last = mid - 1;
        }

        else
        {
            //the index is mid, not mynumbers[mid], and you need to break here
            //once found or it's an infinite loop once it finds it.
            Label11.Text = "Target " + item + " was found at index " + mid;
            break;
        }
    }

Et en fait, je serais probablement un bool drapeau au lieu de garder l'algorithme pure et mélangez pas les trouver à la sortie des préoccupations, ce sera aussi plus facile de dire ce qui s'est passé, si vous quittez la boucle avec non trouvé:

    bool found = false;

    //for a sorted array with descending values
    while (!found && first<=last)
    {
        mid = (first + last) / 2;

        if (target < mynumbers[mid])
        {
            first = mid + 1;
        }

        if (target > mynumbers[mid])
        {
            last = mid - 1;
        }

        else
        {
            //You need to stop here once found or it's an infinite loop once it finds it.
            found = true;
        }
    }

    Label11.Text = found 
        ? "Item " + item + " was found at position " + mid
        : "Item " + item + " was not found";

OriginalL'auteur James Michael Hare

C'est une seule est la bonne :

si target< mynumbers[mid] alors vous avez à prendre de la dernière à la mi-1,
parce que nous avons à rechercher dans le bas de la fourchette, c'est à dire de la première à la mi-1

while (first<=last)
        {
            mid = (first + last) / 2;
            if (target == mynumbers[mid])
            Label11.Text = "Target " + item + " was found at index " + mynumbers[mid];

            else if (target < mynumbers[mid])
                last = mid - 1;
            else (target > mynumbers[mid])
                first = mid + 1;

            }

OriginalL'auteur Ravindra Bagale

Sa a fonctionné pour moi

public static int search(int[] arr, int value)
{
    Debug.Assert(arr.Length>0);
    var left = 0;
    var right = arr.Length - 1;

    while (((right - left)/2) > 0)
    {
        var middle = left + (right - left)/2;
        if (arr[middle] < value)
            left = middle + 1;
        else
            right = middle;
    }
    return arr[left] >= value ? left : right;
}

OriginalL'auteur dprotopopov

public static object BinnarySearch(int[] array,int SearchKey)
    {
        int min = 0;
        int max = array.Length - 1;
        while (min <= max)
        {
            int mid = (min + max) / 2;
            if (SearchKey == array[mid])
            {
                return mid;
            }
            else if (SearchKey < array[mid])
            {
                max = mid - 1;
            }
            else
                min = mid + 1;
        }
        return "Not Found";
    }

OriginalL'auteur Tural_M