Список вопросов
Как зайти в Даркнет?!
25th January, 01:11
8
0
Как в tkinter из поля ввода Entry получить значение в одну переменную и обновить строку кнопкой, затем получить ещё одно введённое значение и затем сложить их. Ниже пример кода
21st July, 19:00
898
0
Программа, которая создает фейковые сервера в поиске игровых серверов CS 1.6 Steam
21st March, 17:43
951
0
Очень долго работает Update запрос Oracle
27th January, 09:58
916
0
не могу запустить сервер на tomcat HTTP Status 404 – Not Found
21st January, 18:02
907
0
Где можно найти фрилансера для выполнения поступающих задач, на постоянной основе?
2nd December, 09:48
941
0
Разработка мобильной кроссплатформенной военной игры
16th July, 17:57
1726
0
период по дням
25th October, 10:44
3957
0
Пишу скрипты для BAS только на запросах
16th September, 02:42
3722
0
Некорректный скрипт для закрытия блока
14th April, 18:33
4614
0
прокидывать exception в блоках try-catch JAVA
11th March, 21:11
4382
0
Помогите пожалуйста решить задачи
24th November, 23:53
6087
0
Не понимаю почему не открывается детальное описание продукта
11th November, 11:51
4352
0
Нужно решить задачу по программированию на массивы
27th October, 18:01
4398
0
Метода Крамера С++
23rd October, 11:55
4309
0
помогите решить задачу на C++
22nd October, 17:31
4002
0
Помогите решить задачу на python с codeforces
22nd October, 11:11
4492
0
Python с нуля: полное руководство для начинающих
18th June, 13:58
2599
0
Помогите с алгоритмом
Просмотров: 329
 
Ответов: 3
Есть упорядоченный массив целых чисел и ещё два целых числа, задающие некоторый интервал. Нужно с помощью алгоритма бинарного поиска определить сколько чисел из массива принадлежат заданному интервалу.
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;
Все очень просто. С помощью алгоритма бинарного поиска находите сначало первое число, потом второе.
Разница их индексов и будет искомым количеством. В завимости от точной постановки может нужно будет убрать еденицу.
Подозреваю что язык паскаль. Тогда код поиска будет подобен этому.
{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;
Чтобы ответить на вопрос вам нужно войти в систему или зарегистрироваться