0 like 0 dislike
29 views
There is an ordered array of integers and two integers that specify a certain interval. Should be using the binary search algorithm to determine how many numbers from the array belong to a given interval.
| 29 views

0 like 0 dislike
`static int the 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 = the BinarySearch(A, left); int rightIndex = the BinarySearch(A, right + 1); int countBetweenLeftAndRight = rightIndex - leftIndex; `
by
0 like 0 dislike
It's very simple. Using the binary search algorithm to first find the first number, then second.
The difference of their indices will be sought. In zavimosti on the exact definition may need to clean the unit.
I suspect that the language Pascal. Then the code search will be similar to that.
\r
{foo — the desired quantity. a and b — the border of the search}
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;
by
0 like 0 dislike
If the language allows (C, for example), one can speed up the finding of the second number after the first is found by setting search shorter.
\r
Although modern smart processors, this will not necessarily be faster.
by

0 like 0 dislike