Реализация C lower_bound

Question

На основании найденного определения здесь

Возвращает итератор, указывающий на первый элемент в отсортированном диапазоне [первый, последний), который не сравнивается меньше стоимости. Сравнение сделано с использованием любого оператора <для первая версия или комп для второй. </p>

Какая будет C-эквивалентная реализация lower_bound (). Я понимаю, что это будет модификация бинарного поиска, но не могу точно определить точную реализацию.

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

Вот эквивалентные реализации upper_bound и lower_bound.Этот алгоритм имеет O (log (n)) в худшем случае, в отличие от принятого ответа, который в худшем случае получает O (n).

Обратите внимание, что здесь high index установлен на 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 ++ работает для всех контейнеров.Вы можете найти это здесь .

Answer 2

lower_bound почти как обычный двоичный поиск, за исключением:

1. Если элемент не найден, вы возвращаете свое текущее место в поиске, а не возвращаете какое-либо нулевое значение.
2. Если элемент найден, вы будете искать влево, пока не найдете несоответствующий элемент.Затем вы возвращаете указатель / итератор на первый соответствующий элемент.

Да, это действительно так просто.: -)

Answer 3

Функции lower_bound и upper_bound в python будут реализованы следующим образом:

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 4

Я знаю, что это очень старый пост. Тем не менее, я работал над проблемой, и я наткнулся на этот пост. Я хотел бы добавить свою итеративную версию для задачи, которая является расширением последнего ответа. Я проверил это с помощью тестовых случаев, которые я мог придумать. Я приложил свой код в 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

Answer 5

Пример, если это заданный массив

1 2 3 3 4

и различные значения x равны

3, тогда firstOccurance будет2 и lastOccurance будет 3

2, затем firstOccurance будет 1 и lastOccurance будет 1

10, затем firstOccurance будет -1, а lastOccurance будет -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;
}

Answer 6

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

Редактировать: Исправлена ​​ошибка для несуществующего значения.

Answer 7

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