Сведения о вопросе

Life

20:33, 15th August, 2020

Теги

Помогите с алгоритмом

Просмотров: 329   Ответов: 3

Есть упорядоченный массив целых чисел и ещё два целых числа, задающие некоторый интервал. Нужно с помощью алгоритма бинарного поиска определить сколько чисел из массива принадлежат заданному интервалу.



  Сведения об ответе

PAGE

09:18, 6th August, 2020

    static int binarySearch(int[] A, int n) {
        int left = 0;
        int right = A.length;
        if (right == 0 || n > A[right - 1]) {
            return right;
        }

        while (left < right - 1) {
            int mid = (left + right) / 2;
            if (A[mid] <= n) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return A[left] >= n ? left : right;
    }

    int leftIndex = binarySearch(A, left);
    int rightIndex = binarySearch(A, right + 1);
    int countBetweenLeftAndRight = rightIndex - leftIndex;


  Сведения об ответе

DINO

09:24, 12th August, 2020

Все очень просто. С помощью алгоритма бинарного поиска находите сначало первое число, потом второе.
Разница их индексов и будет искомым количеством. В завимости от точной постановки может нужно будет убрать еденицу.
Подозреваю что язык паскаль. Тогда код поиска будет подобен этому.

{foo — искомая величина. а и б — границы поиска}
procedure Find(foo: integer; a: integer; b: integer);
var c: integer;
begin
if (b-a) > 1 then
begin
c:= (a+b) div 2;
find(foo,a,c);
find(foo,c,b);
end else
begin
if (array_[a] = foo) then Result := a;
if (array_[b] = foo) then Result := b;
end;
end;


  Сведения об ответе

FAriza

12:35, 16th August, 2020

Если язык позволяет (C, например), можно несколько ускорить нахождение второго числа после того, как найдено первое, задав для поиска меньший интервал.

Хотя на современных шибко умных процессорах это не обязательно будет быстрее.


Ответить на вопрос

Чтобы ответить на вопрос вам нужно войти в систему или зарегистрироваться