c - Clower_boundの実装

Question

ここにある次の定義に基づいています

値未満を比較しない、ソートされた範囲[first、last）の最初の要素を指すイテレーターを返します。比較は、最初のバージョンの場合はoperator <、2番目のバージョンの場合はcompのいずれかを使用して行われます。

lower_bound（）のCと同等の実装は何でしょうか。二分探索の修正になることは理解していますが、正確な実装を正確に特定することはできないようです。

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

サンプルケース：

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; 

私が試したコードを以下に示します。

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);

}

Answer 1

lower_bound通常の二分探索とほとんど同じですが、次の点が異なります。

1. 要素が見つからない場合は、null 値を返すのではなく、検索で現在の場所を返します。
2. 要素が見つかった場合は、一致しない要素が見つかるまで左方向に検索します。次に、最初に一致した要素へのポインター/イテレーターを返します。

はい、それは本当に簡単です。:-)

Answer 2

Pythonのlower_boundandupper_bound関数は、次のように実装されます。

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)

Answer 3

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;
}