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

Groups > comp.programming > #2815

Re: Need Help With Algorithm

Show all headers | View raw

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;

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