Thread: Running time question.

Why not just binary search for a, binary search for b, and subtract the index of a from the index of b?

Array is in sorted order so the difference of indexes must be the number of elements between them. I'd be careful of duplicate values though. Specifically if a and b are not unique in the array.

No. You can't use that approach full stop because you aren't achieving the running time that you wanted. You don't know how many elements are between a and b so your loop could end up running a worst case of O(N) times. This would make your running time O(N) + O(logN).

You need to use the approach specified in my above post, unless you can think of something else.

I am not quite sure I am following. Let me see whether I correctly understood what you wrote. Were you implying something like this:

Code:

Range(Input: integer n, sorted array A, integer a, integer b){
  i  <-  BinarySearch(n,A,A[i]>=a)
  j  <-  BinarySearch(n,A,[A]<=b)
  num  <-  1 + j - i
  output(num)
}

It's not clear what the third argument you're supplying is but if you just supply a on the first call and b on the second then that is correct. Again though, extra care needs to be taken if duplicate values exist in the array (see c99tutorial's post).

I was actually trying to surmount the duplicate values problem by locating the first occurence of A[i]>=a thus:

Code:

BinarySearch(n,A,A[i]>=a)

That couldn't work, could it? :-)
Suppose I didn't wish to alter my array, is there a way to locate the first occurence of A[i]>=a without using a loop? However, once I use a loop, wouldn't that entail exceeding the running time restrictions?

Well I mean parameters are just passed by value and it's not like you can pass the index because if you had the index then you wouldn't need to call the function . I know that it's just pseudocode so it's pretty flexible but this very well might change the running time of the programming and isn't as trivial as it first looks so it's worth saying how you would locate the first occurrence of a duplicate element.

It's likely that if this is an assignment then it says somewhere that there are no duplicates. If not (or if it's not an assignment, or if you want to figure it out anyways!) then I'd probably consider going past the element in my binary search and then backtracking if a same-valued element is not found. Recursion would work well for this. You'd have to have two different methods for if you want to find the index of the first or the last duplicate though. It's not really a particularly elegant solution to the problem and other people might have something better. This would make your implementation consistently perform it's worst case but it would still be more or less logN time.

Unfortunately, there ARE duplicates in the array (the assignment indicates so). I wrote the following, which seems to work (I have tried it on several arrays), yet am not sure it's infallible:

Code:

min  <- 1
max  <- n
while (min<=max){
  mid  <-  |_(min+max)/2_|
  if (A[mid]<a)
    min  <-  mid+1
  else
    max  <-  mid-1
}
output(min)

What do you think? Does it seem okay?
Obviously, in case it works, I could implement pretty much the same for finding the last recurrence of b and that concludes the task.

I think that that works. Nice solution.