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

Groups > comp.programming > #2790 > unrolled thread

Need Help With Algorithm

Back to article view | Back to comp.programming

Contents

  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

#2790 — Need Help With Algorithm

A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,

  5,3,1,2,3,4,7

is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.

Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.

For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 

This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest. 

BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.

[toc] | [next] | [standalone]

#2791

On Thu, 10 Jan 2013 19:21:31 -0800 (PST), willmann817
<willmann817@gmail.com> wrote:

>A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
>
>  5,3,1,2,3,4,7
>
>is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
>
>Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
>
>For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 
>
>This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest. 
>
>BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.


A hint:  given your constraints, what do you know about the slope of
the line near the mid-point of a binary search iteration?  What does
that slope's relationship to the other two points imply?  And how
would you determine the slope at that point?

[toc] | [prev] | [next] | [standalone]

#2792

On Jan 11, 3:21 am, willmann817 <willmann...@gmail.com> wrote:
> A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
>
>   5,3,1,2,3,4,7
>
> is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
>
> Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
>
> For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.)
>
> This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest.
>
> BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.

A couple of suggestions:

Pick a point in the middle. Compare its value with the next one, to
see if you are going up or down. Thus you can deduce whether this
middle point is before or after the lowest, and so halve the places
where the lowest might be.

Alternatively, measure a value about a third of the way in, call it a,
and about two thirds, call it b. If the value of a is lower, the
minimum is before b, and vice versa. So you have a smaller range to
worry about (but this time two thirds of the size, so arguably not a
binary search).

Hope that helps.
Paul.

[toc] | [prev] | [next] | [standalone]

#2802

On Jan 11, 7:05 pm, Paul N <gw7...@aol.com> wrote:
> On Jan 11, 3:21 am, willmann817 <willmann...@gmail.com> wrote:
> > Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
>
> > BUT!!!!!! The solutions to the problem MUST involve binary search...
>
> Alternatively, measure a value about a third of the way in,...

I assume that by "about a third" you mean "about 38.2%"  :-)
... and repeat this probe ratio recursively.

Voilà the famous Golden Ratio search !

James

[toc] | [prev] | [next] | [standalone]

#2794

On Thursday, January 10, 2013 10:21:31 PM UTC-5, willmann817 wrote:
> A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
> 
> 
> 
>   5,3,1,2,3,4,7
> 
> 
> 
> is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
> 
> 
> 
> Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
> 
> 
> 
> For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 
> 
> 
> 
> This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest. 
> 
> 
> 
> BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.

Thanks Paul and Robert!  I will get back to you with a pseudo code solution and if it still needs work I might ask for more hints.

[toc] | [prev] | [next] | [standalone]

#2798

On Friday, January 11, 2013 11:02:57 AM UTC-5, willmann817 wrote:
> On Thursday, January 10, 2013 10:21:31 PM UTC-5, willmann817 wrote:
> 
> > A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
> 
> > 
> 
> > 
> 
> > 
> 
> >   5,3,1,2,3,4,7
> 
> > 
> 
> > 
> 
> > 
> 
> > is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
> 
> > 
> 
> > 
> 
> > 
> 
> > Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
> 
> > 
> 
> > 
> 
> > 
> 
> > For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 
> 
> > 
> 
> > 
> 
> > 
> 
> > This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest. 
> 
> > 
> 
> > 
> 
> > 
> 
> > BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.
> 
> 
> 
> Thanks Paul and Robert!  I will get back to you with a pseudo code solution and if it still needs work I might ask for more hints.


Here is the problem statement and below it is my current non working solution:

 A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,

  5,3,1,2,3,4,7

is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.

Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.

For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 

 function V_Min(A : Int_Array) return Integer is
   lo : Integer := A'First;
	hi : Integer := A'Last;
	mid: Integer := A(lo+hi)/2;

	begin
	
	if A'length = 1 then
		return A(A'First);
	elsif A'length = 2 then
		return Integer'Max(A(A'First),A(A'Last));
	end if;
	
	if A(mid) < A(mid - 1) and A(mid) < A(mid + 1) then
		return A(mid);
	elsif A(mid) > A(mid - 1) then
		hi := mid - 1;
		return V_Min(A(lo..hi));
	else 
		lo := mid + 1;
		return V_Min(A(lo..hi));
   end if;
   end V_Min;

[toc] | [prev] | [next] | [standalone]

#2799

willmann817 <willmann817@gmail.com> writes:

<snip>
> Here is the problem statement and below it is my current non working solution:
>
>  A V-shaped sequence consists of a (possibly empty) decreasing
>  sequence followed by a (possibly empty) increasing sequence. For
>  example,
>
>   5,3,1,2,3,4,7
>
> is a V-shaped sequence, consisting of the decreasing sequence 5,3,1
> followed by the increasing sequence 2,3,4,7. Alternatively, it can be
> viewed as the decreasing sequence 5,3 followed by the increasing
> sequence 1,2,3,4,7.
>
> Given an array containing a V-shaped sequence, find and return the
> minimum value in the sequence. For example, given the above sequence,
> you would return 1.
>
> For simplicity, you can assume that the array is non-empty and that no
> two consecutive values are equal. (Non-consecutive values may be
> equal, such as the 3s in the above sequence.)
>
>  function V_Min(A : Int_Array) return Integer is
>    lo : Integer := A'First;
> 	hi : Integer := A'Last;
> 	mid: Integer := A(lo+hi)/2;

Stare at this line until you see what's wrong!

> 	begin
> 	
> 	if A'length = 1 then
> 		return A(A'First);
> 	elsif A'length = 2 then
> 		return Integer'Max(A(A'First),A(A'Last));

And then review this one.

> 	end if;
> 	
> 	if A(mid) < A(mid - 1) and A(mid) < A(mid + 1) then
> 		return A(mid);
> 	elsif A(mid) > A(mid - 1) then
> 		hi := mid - 1;
> 		return V_Min(A(lo..hi));
> 	else 
> 		lo := mid + 1;
> 		return V_Min(A(lo..hi));
>    end if;
>    end V_Min;
>

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#2800

On 1/12/2013 6:51 AM, Ben Bacarisse wrote:
> willmann817 <willmann817@gmail.com> writes:
...
>>   function V_Min(A : Int_Array) return Integer is
>>     lo : Integer := A'First;
>> 	hi : Integer := A'Last;
>> 	mid: Integer := A(lo+hi)/2;
>
> Stare at this line until you see what's wrong!

If staring does not work, try giving your variables longer, more
explicit, names.

Patricia

[toc] | [prev] | [next] | [standalone]

#2806

On Thursday, January 10, 2013 10:21:31 PM UTC-5, willmann817 wrote:
> A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
> 
> 
> 
>   5,3,1,2,3,4,7
> 
> 
> 
> is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
> 
> 
> 
> Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
> 
> 
> 
> For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 
> 
> 
> 
> This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest. 
> 
> 
> 
> BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.

Here is my most up to date solution and I made some simple stupid mistakes that I fixed but I am having trouble with when mid, lo and hi are all the same value.  My algorithm attempts to check the neighbors of mid but cannot do so because the array is now at length=1.  Here is my algorithm currently:

   function V_Min(A : Int_Array) return Integer is
   --These 3 values are the indices
   lo : Integer := A'First;
 	hi : Integer := A'Last;
	mid: Integer := lo+hi/2;


	begin

	if A'length = 1 then
		return A(lo);
	elsif A'length = 2 then
		return Integer'Min(A(lo),A(hi));
	else
		put("lo="); New_Line; put(lo);New_Line;
		put("hi="); New_Line; put(hi);New_Line;
		put("mid="); New_Line; put(mid);New_Line;
		if A(mid) < A(mid-1) and A(mid) < A(mid+1) then
			return A(mid);
		elsif A(mid) > A(mid - 1) then
			hi := mid - 1;
			return V_Min(A(lo..hi));
		else --this else statement is the final case:A(mid) > A(mid+1)
			lo := mid + 1;
			return V_Min(A(lo..hi));
   	end if;
	end if;
   end V_Min;

[toc] | [prev] | [next] | [standalone]

#2808

willmann817 writes:

> 	mid: Integer := lo+hi/2;

Most likely needs parentheses.

[toc] | [prev] | [next] | [standalone]

#2809

On Sunday, January 13, 2013 10:57:31 AM UTC-5, Jussi Piitulainen wrote:
> willmann817 writes:
> 
> 
> 
> > 	mid: Integer := lo+hi/2;
> 
> 
> 
> Most likely needs parentheses.

You are the best!!!!!! That was the problem! How did I miss something so obvious! I love you ha ha

[toc] | [prev] | [next] | [standalone]

#2807

On Thursday, January 10, 2013 10:21:31 PM UTC-5, willmann817 wrote:
> A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
> 
> 
> 
>   5,3,1,2,3,4,7
> 
> 
> 
> is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
> 
> 
> 
> Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
> 
> 
> 
> For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 
> 
> 
> 
> This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest. 
> 
> 
> 
> BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.

This is the test case that I cannot get to pass:
 A = (31,30,15,13,12,15,17)
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. 

[toc] | [prev] | [next] | [standalone]

#2811

On 13-Jan-13 16:52 PM, willmann817 wrote:
> On Thursday, January 10, 2013 10:21:31 PM UTC-5, willmann817 wrote:
>> A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
>>
>>
>>
>>    5,3,1,2,3,4,7
>>
>>
>>
>> is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
>>
>>
>>
>> Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
>>
>>
>>
>> For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.)
>>
>>
>>
>> This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest.
>>
>>
>>
>> BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.

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.

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).

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.

[Jw]

[toc] | [prev] | [next] | [standalone]

#2813

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

[toc] | [prev] | [next] | [standalone]

#2815

On Thursday, January 10, 2013 10:21:31 PM UTC-5, willmann817 wrote:
> A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
> 
> 
> 
>   5,3,1,2,3,4,7
> 
> 
> 
> is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
> 
> 
> 
> Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
> 
> 
> 
> For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 
> 
> 
> 
> This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest. 
> 
> 
> 
> BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.

SOLUTION!!
   -- <Running Time = O(log n)>
   function V_Min(A : Int_Array) return Integer is
   --These 3 values are the indices
   lo : Integer := A'First;
 	hi : Integer := A'Last;
	mid: Integer := (lo+hi)/2;
	begin
	if A'length = 1 then
		return A(lo);
	elsif A'length = 2 then
		return Integer'Min(A(lo),A(hi));
	else

		if A(mid) < A(mid-1) and A(mid) < A(mid+1) then
			return A(mid);
		elsif A(mid) > A(mid - 1) then
			hi := mid - 1;
			return V_Min(A(lo..hi));
		else -- A(mid) > A(mid+1)
			lo := mid + 1;
			return V_Min(A(lo..hi));
   	end if;
	end if;
   end V_Min;

[toc] | [prev] | [next] | [standalone]

#2816

On Thursday, January 10, 2013 10:21:31 PM UTC-5, willmann817 wrote:
> A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
> 
> 
> 
>   5,3,1,2,3,4,7
> 
> 
> 
> is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
> 
> 
> 
> Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
> 
> 
> 
> For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 
> 
> 
> 
> This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest. 
> 
> 
> 
> BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.

   function V_Min(A : Int_Array) return Integer is
   --These 3 values are the indices
   lo : Integer := A'First;
 	hi : Integer := A'Last;
	mid: Integer := (lo+hi)/2;
	begin
	if A'length = 1 then
		return A(lo);
	elsif A'length = 2 then
		return Integer'Min(A(lo),A(hi));
	else
		if A(mid) < A(mid-1) and A(mid) < A(mid+1) then
			return A(mid);
		elsif A(mid) > A(mid - 1) then
			hi := mid - 1;
			return V_Min(A(lo..hi));
		else -- A(mid) > A(mid+1)
			lo := mid + 1;
			return V_Min(A(lo..hi));
   	end if;
	end if;
   end V_Min;

[toc] | [prev] | [next] | [standalone]

#2817

On Monday, January 14, 2013 8:27:07 PM UTC-5, willmann817 wrote:
> On Thursday, January 10, 2013 10:21:31 PM UTC-5, willmann817 wrote:
> 
> > A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,
> 
> > 
> 
> > 
> 
> > 
> 
> >   5,3,1,2,3,4,7
> 
> > 
> 
> > 
> 
> > 
> 
> > is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.
> 
> > 
> 
> > 
> 
> > 
> 
> > Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.
> 
> > 
> 
> > 
> 
> > 
> 
> > For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.) 
> 
> > 
> 
> > 
> 
> > 
> 
> > This would be easy normally: There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest. 
> 
> > 
> 
> > 
> 
> > 
> 
> > BUT!!!!!! The solutions to the problem MUST involve binary search in some essential way.  Any ideas?  I do not need code: just help with an algorithm in English or at least a starting point. Thanks for your help.
> 
> 
> 
>    function V_Min(A : Int_Array) return Integer is
> 
>    --These 3 values are the indices
> 
>    lo : Integer := A'First;
> 
>  	hi : Integer := A'Last;
> 
> 	mid: Integer := (lo+hi)/2;
> 
> 	begin
> 
> 	if A'length = 1 then
> 
> 		return A(lo);
> 
> 	elsif A'length = 2 then
> 
> 		return Integer'Min(A(lo),A(hi));
> 
> 	else
> 
> 		if A(mid) < A(mid-1) and A(mid) < A(mid+1) then
> 
> 			return A(mid);
> 
> 		elsif A(mid) > A(mid - 1) then
> 
> 			hi := mid - 1;
> 
> 			return V_Min(A(lo..hi));
> 
> 		else -- A(mid) > A(mid+1)
> 
> 			lo := mid + 1;
> 
> 			return V_Min(A(lo..hi));
> 
>    	end if;
> 
> 	end if;
> 
>    end V_Min;

The Programming Language is  Ada2012 if anyone is asking.  Very similar to Ada95 and 2005

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web