Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #2813

Re: Need Help With Algorithm

Show all headers | View raw

Jongware <jongware@no-spam.plz> writes:

> On 13-Jan-13 16:52 PM, willmann817 wrote:
> You are contradicting yourself. Please explain this:
>
>> This is the test case that I cannot get to pass:
>>   A = (31,30,15,13,12,15,17)
>
> (one can find the length of the array is '7' by counting the number of
> elements)
>
>> What happens is lo, hi and mid are all equal to 4 and then this line:
>> if A(mid) < A(mid-1) and A(mid) < A(mid+1) then
>> tries to check the neighbors of the Array when the array is only of
> length 1 (it has no neighbors) so I get an index check failure.  How can
> I fix this.
>
> So now the array length turns out to be '1'? In that case, the value of
> lo, hi, and mid can never be '4', meaning there is a relatively large
> failure in your program, in your hardware (unlikely) or in your logic.

I suspect the above response will confuse the OP.
He's not contradicting himself.

The algorithm is recursive.  He starts out with an array of length 7,
and recurses on slices until he's got an array of length 1.
The lower and upper bounds of that array are 4.

> An array length of '1' is a degenerate case, and so you could treat it
> as such. If your array has a length of 1 then the return value is simply
> A[0], i.e., the only value is the minimum (coincidentally, it's also the
> maximum *and* the mathematical average).

No, this isn't C!  Nor C++, Java, C#, etc.

> If your array has a length of two, it's still a degenerate case. In that
> case you'd return the smallest value of the two.
>
> Rather than hard-wiring these two as 'exceptions', I'd suggest you
> investigate what logic you can build into your existing program to
> handle these boundary cases.

A recursive algorithm generally needs at least one "base case".

My advice to the OP:

First write a normal binary search, and get it working.
Search an array of integers that is in increasing order.
Test all the boundary conditions you can think of.

Then adapt it to the "V-shaped" problem you're trying to solve.

"lo+hi/2" probably isn't what you want -- "/" is higher precedence
than "+".

"(lo+hi)/2" can overflow for large arrays.

Indent using spaces, not tabs.

Especially don't post examples containing tabs, because some
software between you and your readers is bound to evilly mess
up the indentation.

Use Natural and Positive where appropriate, rather than Integer.
Consider using user-defined integer types.

You don't need to calculate lo/hi/mid until after the base case(s).
Then you can move their declarations into a more-local scope,
and you can make them 'constant'.

There's an interesting article about the pitfalls of
binary search here:

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html#!/2006/06/extra-extra-read-all-about-it-nearly.html

But you probably ought to try to figure it out on your own
before reading that.

- Bob

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Need Help With Algorithm willmann817 <willmann817@gmail.com> - 2013-01-10 19:21 -0800
  Re: Need Help With Algorithm Robert Wessel <robertwessel2@yahoo.com> - 2013-01-10 21:51 -0600
  Re: Need Help With Algorithm Paul N <gw7rib@aol.com> - 2013-01-11 04:05 -0800
    Re: Need Help With Algorithm James Dow Allen <jdallen2000@yahoo.com> - 2013-01-13 01:28 -0800
  Re: Need Help With Algorithm willmann817 <willmann817@gmail.com> - 2013-01-11 08:02 -0800
    Re: Need Help With Algorithm willmann817 <willmann817@gmail.com> - 2013-01-12 04:39 -0800
      Re: Need Help With Algorithm Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-01-12 14:51 +0000
        Re: Need Help With Algorithm Patricia Shanahan <pats@acm.org> - 2013-01-12 10:16 -0800
  Re: Need Help With Algorithm willmann817 <willmann817@gmail.com> - 2013-01-13 07:48 -0800
    Re: Need Help With Algorithm Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-01-13 17:57 +0200
      Re: Need Help With Algorithm willmann817 <willmann817@gmail.com> - 2013-01-13 08:47 -0800
  Re: Need Help With Algorithm willmann817 <willmann817@gmail.com> - 2013-01-13 07:52 -0800
    Re: Need Help With Algorithm Jongware <jongware@no-spam.plz> - 2013-01-14 15:42 +0100
      Re: Need Help With Algorithm Robert A Duff <bobduff@shell01.TheWorld.com> - 2013-01-14 12:14 -0500
  Re: Need Help With Algorithm willmann817 <willmann817@gmail.com> - 2013-01-14 17:26 -0800
  Re: Need Help With Algorithm willmann817 <willmann817@gmail.com> - 2013-01-14 17:27 -0800
    Re: Need Help With Algorithm willmann817 <willmann817@gmail.com> - 2013-01-14 17:30 -0800

csiph-web