This is not a Java question but it is a computer science question in general (but if you help me with my solution we can write it in java or pseudo code if you want). If there is a more appropriate place to write this thread please let me know and I will move it.

If there is anyone who is really knowledgeable on algorithms that would be wonderful. If I am given an array and it is V-Shaped (meaning the values start off smaller, then hit a minimum value and then increase again) how can I find the minimum value. It is possible that there is only 1 value in the array. It is also possible the smallest value is the first value and they only get bigger. You can assume that the array is not empty and that no two consecutive values are equal but non consecutive values can be equal. Here is an example:

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.

Why is this a challenge?

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

Whoops I forgot the caveat:

The algorithm must include some form of Binary Search.

Well haven't worked this completely out, but hope this helps. If you look at the center 3 values, the smallest one among the 3 is either in the center, left or right

If in center, you got your min
If left, you are in the right arm of your V, so recurse left
If right, you are in the left arm of your V, so recurse right

normally, a binary search would look at THE element at the center(-ish, if there are an even number of elements left). I don't think that is enough here.

I think you have to look at more than one element each time - the midpoint element and the elements on either side to see which side you need to divide in half next (or if you are done.

edit - I didn't fully read Jayesh's reply, but I think we are saying basically the same thing.

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

Thanks guys, I will come up with a pseudo code solution and I will post back and show you what I have and let you know if it works or not or if I need some help. Thanks again.

Bill, are you the zillionare member of the Koch brothers? Good to see you working at algorithms.

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

Pat, I totally wish I was right now. I hate school. Unfortunately I can't teach myself Object Oriented Programming (which is in Java) or Algorithms (oh which by the way is all in Ada). So those are my two weak classes. And even if I wanted to take them I would hire you guys here at the ranch to be my tutors ha ha

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

Ok here is my thought: because it has to utilize binary search, you start at the middle. IF there is only one number, it is the smallest. IF their are multiple numbers in the array and number before and number after the middle number are larger than the middle number, than the middle number is the smallest.
Otherwise if the middle number is larger than the one before it, we know that the smallest number is to the left(or in the direction of the smaller values since it is a sorted array). So we make our upper bound 1 less than our current index. And our lower bound still remains the first index in the array. We would do the same if the middle number is larger than the one after it, meaning we need to change our lower bound to the 1 more than the center index and the upper bound to the last index. Make sense so far? Problem is I want to do this recursively but I am not sure how because the function (Ada equivalent of a Java method) only takes in an Integer Array. Here is what I have so far (Ada is pretty easy to read so you shouldnt have a problem if you know Java):

I need to put something after the elsif and the else statements in order to make a recursive call that keep the values of hi and lo and uses them when I pass in the same array. I thought about creating a new array but I do not know if that would hurt my goal of reaching O(log n) running time. Also I can only pass in an Array in this function. I can't add in paramters for the function except the array.

Or you can pass the first and last as parameters to the method instead of getting it from the array

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

Jayesh,

There is a way. I figured it out. Here is what the problem statement is, and below it is my current solution that currently does not pass any test cases:

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

Current Non Working Solution:

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); --A'First & A'Last return the first and last index so for example A(A'First) returns the value inside the first index and A(4) would return the value inside index number 4. In Ada Arrays can begin at 0 or 1 so to be safe I always use A'First to reference the first index.
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;

1. input: V shape array
2. length is also input? if no - go for linear search no way ..
3. Ya, caveat is that search logic should be binary search so, we can get the smallest number by giving space cost or time cost ... which one you want ?

William, DoesNotWork doesn't help us. Can you explain what test cases you ran and what result you got? Did you try debugging? Is there is a difference in results of you have an array of even length vs odd length. Try with arrays of length 3 and 7 first( because they always yield odd numbered subsets) then try 4 and 8( always even subsets) try 5 and 9 ( this will first have odd numbered subset then even) then try 6 (first even then odd). In each of those cases try putting the smallest number in the center, off center and at the ends.

Also, If a. Length=2 then shouldn't you do integer.min

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

Here is my final working solution and it passes 214/214 test cases! Thanks for all 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; --This was one big problem. I had to put lo + hi in parenthesis which I do not know how I missed something so obvious and yes it was Integer'Min instead of Integer'Max (another stupid mistake)

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 -- A(mid) > A(mid+1)
lo := mid + 1;
return V_Min(A(lo..hi));
end if;
end if;
end V_Min;