Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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)) 
}
share|improve this question
1  
Did you even look at the preview before posting? Please do before you post - what you originally posted was unreadable. –  Oded Feb 23 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 at 10:00
1  
Fair enough - perhaps you should read the formatting help? –  Oded Feb 23 at 10:01
1  
Your worst case execution time is O(n) (if a == A[0] && b == A[n]), so no, your algorithm doesn't meet the requirement of O(log n). –  Bart van Ingen Schenau Feb 23 at 10:08
1  
Code blocks need an empty line before them. Look at my edits to see what I have done. –  Oded Feb 23 at 10:43

1 Answer 1

Yes, the approach you have selected will satisfy the requirement. Each binary search is O(log n), so two of them are still O(log n).

No, you haven't got the code right yet. You've got an off-by-one error in the first block and mangled formatting in the second block. As you're using 1-based subscripting there is probably another off-by-one error in your binary search but until you get the formatting right it's too hard to work out.

Actually, I haven't written a binary search in years. Isn't that what the C/C++ libraries are for?

share|improve this answer
    
I have edited my code to handle the case of duplicate values. Does it seem okay (I have tried it on several arrays but wish to make sure)? –  peripatein Feb 23 at 21:58
    
You fixed one of the off-by-one errors; your pseudo-code still has formatting problems; you don't need two functions, one binary search is enough; and if you tried it you must have written real code, so why not show us what you really wrote? –  david.pfx Feb 25 at 13:06
    
I didn't write any real code. Am not trying to conceal anything. I have tried it on a piece of paper, using a few sample arrays. It did yield the desired reasults in all cases. –  peripatein Feb 25 at 17:05
    
@peripatein: OK, then all I can say is that code doesn't look right. Check this link for one that looks much better to me: en.wikipedia.org/wiki/Binary_search_algorithm (iterative solution) –  david.pfx Feb 26 at 12:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.