CLOWER_Bound 구현

CLOWER_Bound 구현

여기서 발견된 다음 정의에 기초하여

값보다 작은 값을 비교하지 않는 정렬된 범위 [처음, 마지막]의 첫 번째 요소를 가리키는 반복기를 반환합니다.첫 번째 버전의 경우 연산자<을 사용하거나 두 번째 버전의 경우 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);

}

다음은 다음과 같은 구현입니다.upper_bound그리고.lower_bound. 이 알고리즘은 최악의 경우 O(n)에 도달하는 허용된 답과 달리 최악의 경우 O(log(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 - l) / 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 - l) / 2;
        if (x <= a[mid]) {
            h = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

실제 C++ 구현은 모든 컨테이너에 적용됩니다.여기에서 찾을 수 있습니다.

lower_bound는 다음을 제외하고는 거의 일반적인 이진 검색을 하는 것과 같습니다.

1. 요소를 찾을 수 없으면 일부 null 값을 반환하는 대신 검색에서 현재 위치를 반환합니다.
2. 요소가 발견되면 일치하지 않는 요소를 찾을 때까지 왼쪽으로 검색합니다.그런 다음 포인터/반복기를 첫 번째 일치 요소로 반환합니다.

네, 정말 그렇게 간단해요. :-)

나는 이것이 아주 오래된 게시물이라는 것을 알고 있습니다.그런데 제가 문제를 해결하고 있는데 우연히 이 게시물을 보게 되었습니다.마지막 답변의 확장인 문제에 대한 반복 버전을 추가하고 싶습니다.저는 제가 생각할 수 있는 테스트 케이스들로 이것을 확인했습니다.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

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)

C++ 구현

int binary_search_lower_bound(vector<int>& array, int target) {
    int lo = 0, hi = (int)array.size();
    int mid;

    while(lo < hi) {
        mid = lo + ((hi - lo) >> 1);
        int val = array[mid];
        if (target <= val)//array[mid])
            hi = mid;
        else
            lo = mid + 1;
    }

    return lo;
}

편집: 존재하지 않는 값에 대한 버그 수정.

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

주어진 배열일 경우 예제

1 2 3 3 4

그리고 x의 다른 값은

3 그러면 첫 번째 발생이 2이고 마지막 발생이 3이 됩니다.

2 그러면 첫 번째 발생이 1이 되고 마지막 발생이 1이 됩니다.

10 그러면 첫 번째 발생은 -1이고 마지막 발생은 -1입니다.

int firstOccurance(vector<int>& arr, int x){
        int low = 0;
        int high = arr.size();
        int ans=-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(arr[mid]==x)     ans=mid;
            if(arr[mid]>=x)     high=mid-1;
            else    low = mid+1;
        }
        return ans;
    }


int lastOccurance(vector<int>& arr, int x){
    int low = 0;
    int high = arr.size();
    int ans=-1;
    while(low<=high){
        int mid = (low+high)/2;
        if(arr[mid]==x)     ans=mid;
        if(arr[mid]<=x)     low=mid+1;
        else    high = mid-1;
    }
    return ans;
}

저는 이것이 이미 많은 답변이 있는 매우 오래된 게시물이라는 것을 알고 있지만 이 문제도 발견했고 일반적인 솔루션이 필요했기 때문에 gnu stdlib bsearch 기능을 적용하기 위해 manish_s 답변을 사용했습니다.필요한 사람이 있을 경우:

size_t myBsearch (const void *__key, const void *__base, size_t __nmemb, size_t __size,
         __compar_fn_t __compar)
{
  size_t __l, __u, __idx;
  const void *__p;
  int __comparison;
  __l = 0;
  __u = __nmemb;
  while (__l < __u)
    {
    __idx = (__l + __u) / 2;
    __p = (void *)(((const char *)__base) + (__idx * __size));
    __comparison = (*__compar)(__key, __p);
    if (__comparison <= 0)
      __u = __idx;
    else if (__comparison > 0)
      __l = __idx + 1;
    }
  return __l;
}

언급URL : https://stackoverflow.com/questions/6443569/implementation-of-c-lower-bound