CheckWordIsValid uses a linear search, program a binary search instead

From TRCCompSci - AQA Computer Science
Jump to: navigation, search

Here's how to create a binary search:

private static bool CheckWordIsValidBinary(string Word, List<string> AllowedWords)
        {
            bool ValidWord = false;

            int lowerlimit = 0;
            int upperlimit = AllowedWords.Count() - 1;

            while ((ValidWord == false) & (upperlimit != lowerlimit))
            {
                int currentposition = Convert.ToInt32((lowerlimit + upperlimit) / 2);
                string currentWord = AllowedWords[currentposition];

                if (String.Compare(Word, currentWord) == 0)
                {
                    ValidWord = true;
                }
                else if (String.Compare(Word, currentWord) < 0)
                {
                    upperlimit = Convert.ToInt32(upperlimit - 0.5*(upperlimit - lowerlimit));
                }
                else if (String.Compare(Word, currentWord) > 0)
                {
                    lowerlimit = Convert.ToInt32(lowerlimit + 0.5 * (upperlimit - lowerlimit));
                }
            }

            return ValidWord;
        }