На основе следующего определения найдено здесь
Возвращает итератор, указывающий на первый элемент в отсортированном диапазоне [первая, последняя], которая не сравнивается меньше стоимости. Сравнение выполненный с использованием любого оператора < для первая версия, или comp для второго.
Что такое 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);
}
lower_bound почти похож на обычный двоичный поиск, за исключением:
Да, это действительно так просто.: -)
Вот эквивалентные реализации upper_bound и lower_bound. Этот алгоритм O (log (n)) в худшем случае, в отличие от принятого ответа, который попадает в O (n) в худшем случае.
Обратите внимание, что здесь high index устанавливается n вместо n - 1. Эти функции могут возвращать индекс, который выходит за пределы массива. I.e., он вернет размер массива, если ключ поиска не найден и больше, чем все элементы массива.
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;
}
Фактическая реализация С++ работает для всех контейнеров. Вы можете найти здесь здесь.
Функции 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)
Я знаю, что это очень старый пост. Тем не менее, я работал над проблемой, и я столкнулся с этим сообщением. Я хотел бы добавить мою итеративную версию проблемы, которая является продолжением последнего ответа. Я проверил это с примерами тестов, о которых я мог думать. Я добавил код в С#.
Этот код работал для всех диапазонов. Однако диапазон должен находиться в пределах первого индекса до последнего индекса + 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
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;
}
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;
}
Редактировать: Исправлена ошибка для несуществующего значения.
Пример, если это заданный массив
1 2 3 3 4
и разные значения х
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;
}