Re: Finding a maxima with binary search?

CBFalconer wrote
(in article <43D25E16.6D875145@xxxxxxxxx>):

>> Uh, well. If the numbers are actually strictly increasing and
>> decreasing integers, then the first difference tells which way.
>> Hence first difference tells whether the maximum is to the left
>> or to the right of the midpoint, and so in that case binary search
>> is applicable, finding the maximum in O(log n).
>
> You may want to reconsider that statement. Try the sequence:
>
> 1 2 3 4 2

I suspect you could modify the basic approach of a binary search
to adjust itself when the "right side" gets a lower number and
still beat a linear search (for large sequences), but not
knowing the full details of the homework question, I'm not keen
to guess.

:-)

--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw
How 'bout them Horns?





.

Relevant Pages

  • Re: Finding a maxima with binary search?
    ... Suppose I have an integer array ... >> Sorting (required for a binary search) is an Ooperation. ... > decreasing integers, then the first difference tells which way. ...
    (comp.programming)
  • Re: Finding a maxima with binary search?
    ... then the first difference tells which way. ... >> right of the midpoint, and so in that case binary search is applicable, ... >> likely HOMEWORK. ...
    (comp.programming)
  • Re: Algorithm to find break in contiguity
    ... save any significant time by jumping around doing a binary search, ... the missing number hasn't been reached yet) as you are reading. ... If the data is not already in sequence, ... Since you used the word "contiguity" in the Subject field, ...
    (comp.programming)
  • Re: How to get file count under a directory?
    ... what is the largest sequence number of my log file. ... a loop from 1 to like 100000, check if the file exist, if it does ... Yes but a binary search is probably faster. ...
    (microsoft.public.vc.language)
  • Re: Finding a maxima with binary search?
    ... Suppose I have an integer array ... and I think that binary search is the way to go. ... then the first difference tells which way. ... So it would not be helpful to the OP to provide pseudocode. ...
    (comp.programming)