的C實現LOWER_BOUND

Question

基於以下定義中找到here

返回指向 第一個元素在排序範圍 一個迭代[第一，最後一個）不大於比較值 以下。比較結果爲 ，使用<爲 第一個版本，或者爲第二個版本使用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. 如果該元素未找到，您將返回您的c urrent在搜索的地方，而不是返回一些空值。
2. 如果找到該元素，則向左搜索，直到找到不匹配的元素。然後你返回一個指針/迭代器到第一個匹配元素。

是的，這真的很簡單。 :-)

Answer 2

在Python中lower_bound和upper_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; 
} 

Answer 4

下面是upper_bound和lower_bound等效的實施方式。這個算法在最壞的情況下是O（log（n）），而不像在最壞的情況下得到O（n）的公認答案。

請注意，此處high索引設置爲n而不是n - 1。這些函數可以返回超出數組邊界的索引。即，如果找不到搜索關鍵字，它將返回數組的大小，並且它大於所有數組元素。

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

實際的C++實現適用於所有容器。你可以找到它here。

Answer 5

我知道這是一個很老的帖子。但是，我正在研究一個問題，我碰到了這個帖子。我想爲這個問題添加我的迭代版本，這是最後一個答案的延伸。我用我能想到的測試案例進行了檢查。我用C＃附加了我的代碼。

此代碼適用於所有範圍。但是，範圍應該在最後一個指數+1的第一個指數內。如果數組的大小爲N，並且將範圍視爲[0，N]，則搜索空間將在[0，N）內。我知道這很明顯，但它幫助我檢查一些邊緣情況。

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

這裏是我使用的測試情況：

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

考慮搜索元素作爲2：

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

考慮搜索元件5：

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

考慮搜索元素爲1：

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

5考慮搜索元素：

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