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

Question

[shalimo]

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

Answer 1

[apangin]

    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;

Answer 2

[Horse]

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

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

Comments

[Horse]

Если указанные 2 числа не должны быть числами из массива >
f (array_[a] > foo) then Result := a;
if (array_[b] < foo) then Result := b;

[Horse]

Сорри. нахомил. Написал поиск в глубину.
c:= (a+b) div 2;
find(foo,a,c);
find(foo,c,b)
нужно заменит на
if (array_© > foo) then find(foo,c,b)
else find(foo,a,c);

[Horse]

И Опять поспешил.
f (array_[a] = foo) then Result := a
else Result := b;
Тоесть. если искомая величина равна а — начинаем считать с нее. иначе с b.
Для второго числа тоже самое но

f (array_[a] = foo) then Result := b
else Result := a;
Тобиш если foo = b заканчиваем на b, иначе на a

[apangin]

Писать двоичный поиск рекурсией — извращение.

Answer 3

[MikhailEdoshin]

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

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

Comments

[Thongor]

Это обязательно будет быстрее. В среднем на 25%.
Но если вы не ICMщик (а ICMщик такого вопроса не задаст), вам все равно.

[mihaild]

ICM? Может быть ACM?

[mihaild]

Быстрее всего будет так:
1. Делаем бинарный поиск, следя чтобы оба числа оставались на отрезке, пока это возможно.
2. У нас есть отрезок, середина которго правее меньшего числа и левее правого. Делаем по нему два бинпоиска.

Можно оценить экономию: с вероятностью 1/2 (разные половины исходного отрезка) экономим 1 операцию, с вероятностью 1/4 (одна половина, разные четверти) — 2, с вероятностью 1/8 — 3 и т.д. Сумма равна 2.
Этот же способ экономит Log(n) — Log(3/4n) = Log(4/3) ~ 0.4150374992788437 операций.
Впрочем, даже на ACM экономить 2 операции сравнения в бинпоиске вряд ли придется.

[MikhailEdoshin]

Что такое ACM (ICM)? Association for Computing Machinery? :)

[vittore]

асм — ассемблер: Р