Coin Flip (worst cost linear search)

Question

Trying to code this coin flip but im confused at the way the textbook wants it done?

Vulpes · Answer

Well, the coin-flip approach, still uses a linear search to look for X. The only difference from using a 'normal' linear search is that, if the flip yields a head, then the list is searched front to back but, if the flip yields a tail, then its searched from back to front. This means that, if X lies in the first half of the list, a head will find it more quickly than a tail. Conversely, if X lies in the second half of the list, a tail will find it more quickly than a head. It's good practice to check that your arguments are both reasonable and consistent which helps when testing a program. If they aren't then the program might still run but produce obscure bugs which manifest them at a later stage. It's not always necessary to throw exceptions - sometimes you can just substitute 'harmless' values for parameters which are obviously wrong or just return from the method with a special 'error' value. You just have to use your judgement in these situations.

Philip Harris · Answer

That makes sense, I appreciate your help again Vulpes. What I need is more experience I think to become more comfortable with the thought behind the exceptions and such. But if it is true that they need to just be thought out and calculated rationally its not to hard to understand. Thanks again !

Philip Harris · Answer

So this "coin flip" search just makes the most amount of work for a search. Also when you throw all those argument exceptions you are doing that to optimize the code and knock out those instances before having to run through the rest of the code?

Vulpes · Answer

I've had a go at trying to code it as set out in the textbook below. As the algorithm seems to be assuming that list indices are 1-based, whereas in .NET they are 0-based, I've adjusted for that by deducting one from the index. I've also included some code to check the arguments to the method : using System; using System.Collections.Generic; class Program { static Random rand = new Random(); static void Main() { var list = new List {3, 5, 7, 8, 10}; int lower = 1; int upper = list.Count; for(int X = 1; X { int index = CoinFlipSearch(list, lower, upper, X); if (index > 0) { Console.WriteLine("{0} was found in the list at index {1}", X, index); } else { Console.WriteLine("{0} is not in the list", X); } } Console.ReadKey(); } static int CoinFlipSearch(List list, int lower, int upper, int X) { if (list == null || list.Count == 0) throw new ArgumentException("list can't be null or empty"); if (lower if (upper if (upper > list.Count) throw new ArgumentException("upper can't be more than the number of elements in the list"); // To simulate flipping a coin, get a random number between 0 and 1 // Let 0 denote tails and 1 heads int flip = rand.Next(0, 2); // excludes endpoint int index = 0; if (flip == 1) { index = lower; while (upper >= index && list[index - 1] != X) index++; if (index > upper) return 0; else return index; } else { index = upper; while (index >= lower && list[index - 1] != X) index--; if (lower > index) return 0; else return index; } } } The output is: 1 is not in the list 2 is not in the list 3 was found in the list at index 1 4 is not in the list 5 was found in the list at index 2 6 is not in the list 7 was found in the list at index 3 8 was found in the list at index 4 9 is not in the list 10 was found in the list at index 5

Coin Flip (worst cost linear search)

Answers (4)