Hi,
I have an array A of n integers, sorted from min to max, and two numbers a<=b, which are known to be in A. I would like to write a pseudo-code for a procedure whose running time is c1+c2log(n) and which returns the number of elements in A which satisfy a<=A[i]<=b.
I wrote the following but am not sure it satisfies the requirement for the running time and would appreciate some help:
*NB <- denotes an arrow*
Code:
Range(Input: integer n, sorted array A, integer a, integer b){
max <- n
i<-BinarySearch(n,A,a)
num <- 1
while (A[i]<=b and i<=max){
i <- i+1
num <- num+1
}
output(num)
}
where BinarySearch is defined thus:
Code:
BinarySearch(Input: integer n, sorted array of integers A, integer x) {
min <- 1, max <- n, found <- FALSE
while ( found = FALSE and min <= max ) {
mid <- |_(min + max) / 2_|
if (A[mid] = x)
found <- TRUE
else if (x < A[mid])
max <- mid-1
else
min <- mid+1
}
if (found = TRUE)
output(mid)
else
output(NOT-FOUND)
}