# Running time question

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

``````LBound(Input: integer n, sorted array of integers A, integer a) {
min  ← 1
max  ← n
while (min <= max) {
mid  ←  |_(min + max) / 2_|
if (A[mid] < a)
min  ←  mid + 1
else
max  ←  mid - 1
}
output(min)
}
LBound(Input: integer n, sorted array of integers A, integer a) {
min  ← 1
max  ← n
while (min <= max) {
mid  ←  |_(min + max) / 2_|
if (A[mid] > b)
max  ←  mid - 1
else
min  ←  mid + 1
}
output(max)
}
Range(Input: integer n, sorted array of integers A) {
output (1 + UBound(n,A,b) – LBound(n,A,a))
}
``````
• Did you even look at the preview before posting? Please do before you post - what you originally posted was unreadable. – Oded Feb 23 '14 at 9:58
• @Oded Of course I looked at the preview! I have been trying to reformat it to not much avail for the past five minutes. – peripatein Feb 23 '14 at 10:00
• Fair enough - perhaps you should read the formatting help? – Oded Feb 23 '14 at 10:01
• Your worst case execution time is O(n) (if a == A && b == A[n]), so no, your algorithm doesn't meet the requirement of O(log n). – Bart van Ingen Schenau Feb 23 '14 at 10:08
• Code blocks need an empty line before them. Look at my edits to see what I have done. – Oded Feb 23 '14 at 10:43