Находить с помощью бисекции, не останавливаясь

Question

Находить с помощью бисекции, не останавливаясь

У меня есть проблема с этим методом, когда он получает «большой» массив в нем. Когда я ввожу массив с примерно 10 числами, он работает нормально. Но если я вставлю как 10 миллионов номеров или даже 20, метод никогда не закончится, и я не смогу найти проблему.

int bisection(int el, int* a, int n)
{
int i = 0;

if (n <= 0)
{
return -1;
}
else
{

do
{
int mid = (i + n) / 2;
if(el == a[i])
{
return i;
}
else if(el < a[n])
{
n = mid - 1;
}
else if(el > a[i])
{
i = mid + 1;
}

}while(i <= n);
}
}

Я должен найти первый номер, например, если у меня есть в массиве:

indexs:   0 1 2 3 4 5 6 7 8
elements: 1,1,3,3,3,5,6,7,9

И я ищу номер 3, я должен получить это как

result: (index) 2

первое вхождение

3

bisection c++methods

Решение

Другие решения

Вы используете неправильный индекс и условие завершения?

int mid;

do { mid = (i + n) / 2; if(el == a[середина] && (mid == 0 || a[mid-1] < el)) //for first occurence { returnсередина; } else if(el <= a[середина]) { n = mid - 1; } else if(el > a[середина]) { i = mid + 1; } }while(я < N);

return -1;

4

Может быть проблема в максимальном размере int, Вы должны проверить sizeof(int) на вашей архитектуре.

Для вашего алгоритма вы можете сделать что-то вроде этого:

unsigned long int bisection(int value, int* vector, unsigned long int size)
{
unsigned long int left = 0;
unsigned long int right = size-1;
unsigned long int previous_left;
while(left < right)
{
unsigned long int i = (left + right) / 2;
if(value < vector[i])
right = i;
else
{
previous_left = left;
left = i;
}
}
left = previous_left;
while(left < right)
{
unsigned long int i = (left + right) / 2;
if(value == vector[i])
right = i;
else
left = i;
}
return left;
}

0

Источник

Accepted Answer

Ответ myusuf почти правильный, но он не всегда возвращает индекс первого появления. Вот мое предложение:

int bisection(int el, int* a, int n)
{
int i = 0;
while(i < n)
{
// search in range i (inclusive) to n (exclusive)
int mid = (i + n) / 2;
if (el == a[mid] && (mid == 0 || a[mid-1] < el))
return mid;
if (el <= a[mid])
n = mid;
else
i = mid + 1;
};
return -1;
}

2