Implementierung von C lower_bound

Basiert auf der folgenden definition gefunden hier

Gibt einen iterator zeigt auf das
erste element in der sortierten Palette
[first,last), die nicht zu vergleichen
weniger als Wert. Der Vergleich ist
mit einer operator< für die
erste version, oder comp für die zweite.

Was wäre die C gleichwertige Umsetzung von lower_bound(). Ich verstehe, dass es wäre eine Modifikation der binären Suche, aber kann nicht scheinen, um ganz lokalisieren der genauen Umsetzung.

int lower_bound(int a[], int lowIndex, int upperIndex, int e);

Beispiel:

int a[]= {2,2, 2, 7 };

lower_bound(a, 0, 1,2) would return 0 --> upperIndex is one beyond the last inclusive index as is the case with C++ signature.

lower_bound(a, 0, 2,1) would return 0.

lower_bound(a, 0, 3,6) would return 3;
lower_bound(a, 0, 4,6) would return 3;

Mein versuchter code ist unten angegeben:

int low_bound(int low, int high, int e)
{
    if ( low < 0) return 0;
    if (low>=high )
    {
      if ( e <= a[low] ) return low;
      return low+1;
    }
    int mid=(low+high)/2;
    if ( e> a[mid])
        return low_bound(mid+1,high,e);
    return low_bound(low,mid,e);

}

InformationsquelleAutor der Frage Shamim Hafiz | 2011-06-22

  1. 10

    lower_bound ist fast wie ein übliche binäre Suche, außer:

    1. Wenn das element nicht gefunden wird, kehren Sie Ihre aktuelle Position in der Suche, sondern als Rückgabe eines null-Wert.
    2. Wenn das element gefunden wird, suchen Sie nach Links, bis Sie finden Sie eine nicht-matching-element. Dann wieder ein Zeiger/iterator auf das erste passende element.

    Ja, es ist wirklich so einfach. 🙂

    InformationsquelleAutor der Antwort Chris Jester-Young

  2. 34

    Hier sind die äquivalenten Implementierungen von upper_bound und lower_bound. Dieser Algorithmus ist O(log(n)) im schlechtesten Fall, im Gegensatz zu den akzeptierte Antwort, die wird O(n) im schlimmsten Fall.

    Beachten Sie, dass hier high index festgelegt ist n statt n - 1. Diese Funktionen zurückkehren können, ein index, ein jenseits der Grenzen des Arrays. I. e., es wird wieder die Größe des Arrays, wenn der Suchbegriff nicht gefunden, und es ist größer als alle Elemente des Arrays.

    int bs_upper_bound(int a[], int n, int x) {
    int l = 0;
    int h = n; //Not n - 1
    while (l < h) {
        int mid = (l + h) / 2;
        if (x >= a[mid]) {
            l = mid + 1;
        } else {
            h = mid;
        }
    }
    return l;
}

int bs_lower_bound(int a[], int n, int x) {
    int l = 0;
    int h = n; //Not n - 1
    while (l < h) {
        int mid = (l + h) / 2;
        if (x <= a[mid]) {
            h = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

    Den tatsächlichen C++ - Implementierung funktioniert auch für alle anderen Container. Sie finden es hier.

    InformationsquelleAutor der Antwort manish_s

  3. 2

    Den lower_bound und upper_bound Funktionen in python würde wie folgt implementiert werden:

    def binLowerBound(a, lo, hi, x):
  if (lo > hi):
    return hi
  mid = (lo + hi) / 2;
  if (a[mid] == x):
    return binLowerBound(a, lo, mid-1, x)
  elif (a[mid] > x):
    return binLowerBound(a, lo, mid-1, x)
  else:
    return binLowerBound(a, mid+1, hi, x)

def binHigherBound(a, lo, hi, x):
  if (lo > hi):
    return lo
  mid = (lo + hi) / 2;
  if (a[mid] == x):
    return binHigherBound(a, mid+1, hi, x)
  elif (a[mid] > x):
    return binHigherBound(a, lo, mid-1, x)
  else:
    return binHigherBound(a, mid+1, hi, x)

    InformationsquelleAutor der Antwort Pirooz

  4. 1

    Ich weiß, dass dies ein sehr Alter post. Allerdings arbeitete ich an einem problem und ich stieß auf dieses post. Hinzufügen möchte ich, dass mein iterative version für das problem ist eine Erweiterung der letzten Antwort. Ich überprüfte diese mit der test-Fälle, die ich denken konnte. Ich angehängt habe mein code in C#.

    Dieser code war die Arbeit für alle reicht. Jedoch sollte der Bereich sein, in dem der erste index auf den letzten index+1. Wenn das array der Größe N und in Anbetracht Bereich [0,N] der Suchraum wird innerhalb von [0,N). Ich weiß, dass ist ziemlich offensichtlich, aber es hat mir geholfen, die überprüfung einige Grenzfälle.

            static int lower_bound(int[] a, int lo,int hi, int x)
        {
            while (lo < hi) 
            {
                int mid = lo + (hi-lo) / 2;
                if(a[mid]==x)
                {
                    /*when there is a match, we should keep on searching
                    for the next same element. If the same element is not                                                         
                    found, mid is considered as the answer and added to 'hi'
                    Finally 'hi' is returned*/
                    if(a[mid-1]!=x)
                    {
                        hi=mid;
                        break;
                    }
                    else
                        hi=mid-1; 
                }
                else if(a[mid]>x)
                    hi=mid-1;
                else
                    lo=mid+1;
            }
            //if element is not found, -1 will be returned   
            if(a[hi]!=x)
                return -1;
            return hi;
        }
        static int upper_bound(int[] a, int lo,int hi, int x)
        {
            int temp=hi;
            while (lo < hi) 
            {
                int mid = lo + (hi-lo) / 2;
                if(a[mid]==x)
                {
                    /*this section make sure that program runs within        
                    range [start,end)*/
                    if(mid+1==hi)
                    {   
                        lo=mid;
                        break;
                    }
                    /*when there is a match, we should keep on searching
                      for the next same element. If the same element is not                                                         
                      found, mid is considered as the answer and added to
                      'lo'. Finally 'lo' is returned*/ 
                    if(a[mid+1]!=x)
                    {
                        lo=mid;
                        break;
                    }
                    else
                        lo=mid+1;
                }


         else if(a[mid]>x)
             hi=mid-1;
         else
             lo=mid+1;
    }
    //if element is not found, -1 will be returned
    if(a[lo]!=x)
            return -1;
        return lo;
    }

    Hier ist ein test case, die ich verwendet habe:

    Array(a) : 1 2 2 2 2 5 5 5 5
size of the array(a) : 9

    Bedenkt, Suche element 2: 

    upper_bound(a,0,9,2)=4, lower_bound(a,0,9,2)=1

    Bedenkt, Suche element 5: 

    upper_bound(a,0,9,2)=8, lower_bound(a,0,9,2)=5

    Angesichts gesuchten element als 1: 

    upper_bound(a,0,9,2)=0, lower_bound(a,0,9,2)=0

    Bedenkt, Suche element 5: 

    upper_bound(a,5,9,2)=8, lower_bound(a,5,9,2)=5

    InformationsquelleAutor der Antwort K.G aka Confused_Coder

  5. 0
    int lowerBound (int *a, int size, int val) {
   int lo = 0, hi = size - 1;
   while (lo < hi) {
      int mid = lo + (hi - lo)/2;
      if (a[mid] < val)
         lo = mid + 1;
      else
         hi = mid;
   }
   return lo;
}

    InformationsquelleAutor der Antwort mszlazak

Schreibe einen Kommentar