Re: Binary search with timestamps

Miss Elaine Eos wrote:
> In article <5qWdnVOXpYvXyS7aRVnyiwA@[EMAIL PROTECTED]
>, Makhno <root@[EMAIL PROTECTED]
> 
> wrote:
> 
>>> top = array.length
>>> bottom = 0
>>> foundIndex = -1
>>> while (top > bottom)
>>> {
>>>    mid = (top + bottom) / 2
>>>    if array [mid] == desiredValue
>>>       foundIndex = mid
>>>       break
>>>    else if array [mid] > desiredValue
>>>       top = mid
>>>    else
>>>       bottom = mid
>>> }
>>>
>>> return (foundIndex)
>> Afraid this doesn't work, as it assumes desiredValue is an integer, or 
>> at least directly present in the list. eg I could have
>>
>> 0.5
>> 1.2
>> 5.6
>> 5.8
>> 7.4
>> 9.0
>>
>> for desiredValue=6.2 then I would like index 3, because index 3&4 
>> bracket the desiredValue.
> 
> Ah, that wasn't in the original spec.  I thought you were searching for 
> an exact value.
> 
>> It was not as easy as I initially assumed, even though my algorithm 
>> works for most cases.
> 
> If the value does not exist in the array, then what is it you'd like to 
> be returned?  1 greater than the largest index still smaller than the 
> value?  I don't think your other solution (posted after this) does that.
> 

I agree - this is nothing like what you originally asked for.

It is im****tant to define exactly what it is that you want - this 
enables you to test it and know if it is working.

It doesn't have to be elaborate.  For example:

A function which returns the first item in a sorted array greater than 
or equal to a given value.

I work in QA right now, and it is my job to find minor discrepancies 
such as these :)

--
LTP

:)