Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!news-out.readnews.com!transit3.readnews.com!panix!newsfeed-00.mathworks.com!nntp.TheWorld.com!.POSTED!not-for-mail From: Robert A Duff Newsgroups: comp.programming Subject: Re: Need Help With Algorithm Date: Mon, 14 Jan 2013 12:14:43 -0500 Organization: The World Public Access UNIX, Brookline, MA Lines: 79 Message-ID: References: <276b0d44-8d70-4d3e-aacd-47e3321111af@googlegroups.com> <50f41966$0$6933$e4fe514c@news2.news.xs4all.nl> NNTP-Posting-Host: shell01.theworld.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: pcls6.std.com 1358183683 23363 192.74.137.71 (14 Jan 2013 17:14:43 GMT) X-Complaints-To: abuse@TheWorld.com NNTP-Posting-Date: Mon, 14 Jan 2013 17:14:43 +0000 (UTC) User-Agent: Gnus/5.1008 (Gnus v5.10.8) Emacs/21.3 (irix) Cancel-Lock: sha1:H4Pf2unDu+jasSsL1a5xVvoi2Ms= Xref: csiph.com comp.programming:2813 Jongware 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