C# Binary Search returning no result

Question

CODE:

using System;
using System.IO;
using System.Collections.Generic;

class MainClass {
    public static void Main (string[] args) {
        Console.WriteLine ("Get Random Names");
        // Read every line in the file.
        List<string> nameList = new List<string>();
        using (StreamReader reader = new StreamReader("test.txt"))
        {
            string line;
            while ((line = reader.ReadLine()) != null)
        {
            nameList.Add(line);
        }
    }

        nameList.Sort();
        int startValue = 0;
        int middleValue = (nameList.Count + 1) / 2;
        int endValue = (nameList.Count + 1);

        Console.WriteLine("Enter a name to search for.");
        String name = Console.ReadLine();

        bool nameNotFound = true;
        var compareResult = String.Compare(nameList[middleValue], name);


        while (nameNotFound) { 
            if (compareResult < 0) {
              endValue = middleValue;
              middleValue = endValue / 2;
            }
            else if (compareResult > 0) {
              startValue = middleValue;
              middleValue = (endValue - startValue) / 2 + startValue;
            }
            else {
              Console.WriteLine("Name " + name + " was found.");
              nameNotFound = false;
            }
        }
}
}

PROBLEM: I am trying to code a C# binary search that searches a file with a list names (strings). For some reason I can't figure out, the search returns no results. Anyone have any ideas?

SOLUTION: I've fixed the code now. The two problems were that I wasn't comparing the value in the if and else if loops and I had my greater than and less than symbols mixed up.

can you provide example data ? maybe there was no result because there was actually no result ;) — Pac0
– Pac0, Commented Sep 29, 2018 at 10:43
The text file has a list of 20 names. Each name is on a separate line. For example, the 9th name is Marina. When I enter Marina, the program returns no result. — New User
– New User, Commented Sep 29, 2018 at 10:46
You are never recalculating your compareResult in your last while loop. You will be stuck with the compareResult of the first comparison you did before entering the loop. — Pac0
– Pac0, Commented Sep 29, 2018 at 10:48

X39 · Accepted Answer · 2018-09-29 10:50:16Z

1

    int startValue = 0;
    int middleValue = (nameList.Count + 1) / 2; // Here you just take the line
                                                // that was in the middle of the file
    int endValue = (nameList.Count + 1);
    // [...]
    var compareResult = String.Compare(nameList[middleValue], name); // and here you check for it

.

    while (nameNotFound) { // A loop that never compares again
                           // (and makes me wonder how you actually exit the program)
        if (compareResult < 0) {
          endValue = middleValue;
          middleValue = endValue / 2;
        }
        else if (compareResult > 0) {
          startValue = middleValue;
          middleValue = (endValue - startValue) / 2 + startValue;
        }
        else {
          Console.WriteLine("Name " + name + " was found.");
          nameNotFound = false;
        }
    }

The TL;DR is that your code provided only ever checks if the most-middle string in your text document is the same as the name provided

you need to compare (again) for starters

answered Sep 29, 2018 at 10:50

X39

8277 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

New User Over a year ago

Thanks, I have tried changing that but it still isn't returning a result for any of the names.

Pac0 · Accepted Answer · 2018-09-29 10:51:25Z

1

In the main algorithm loop at the end, you are never recalculating the compareResult, so your program cannot tell when it has found something.

You need to add a compareResult = String.compare ... in the if and else if blocks. .

If you don't do that, compareResult will keep the result of the first comparison you did before the loop.

answered Sep 29, 2018 at 10:51

Pac0

23.4k9 gold badges76 silver badges85 bronze badges

8 Comments

New User Over a year ago

Thanks, I have tried changing that but it still isn't returning a result for any of the names

Pac0 Over a year ago

there might be other problems of course. You should use a debugger. go step by step in each line and iteration of your loop, and check that the variables do contain what you think they contain, and that you are actually testing the correct variables. I intentionaly wrote String.compare ... instead of the actual correct code, because it's easy to make a mistake here, and there are several possiblities depending on where exactly did you insert the new lines.

Pac0 Over a year ago

Which software /IDE do you use to program?

New User Over a year ago

I'm using Repl.it

New User Over a year ago

Thanks, I've fixed it now. Turns out compareResult was returning the opposite of what I was expecting - when I was expecting 1 it was returning -1 and vice versa. I've swapped the greater than and less than symbols in the if and else if and it's working great now.

|

Bashar Issa · Accepted Answer · 2018-09-29 12:25:27Z

try to understand the old answers, then try to rewrite enhanced code, if you fail, don't be depressed, look here:

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace StackOverflowSolver
{
    class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Get Random Names");
            // Read every line in the file.
            List<string> nameList = new List<string>();
            using (StreamReader reader = new StreamReader("test.txt"))
            {
                string line;
                while ((line = reader.ReadLine()) != null)
                {
                    nameList.Add(line);
                }
            }

            nameList.Sort();

            //you can get better variables name with replacing Value with Index
            int startValue = 0;
            //int middleValue = (nameList.Count + 1) / 2;   error
            //consider you've three elements, middleValue will be 2 
            //the array index began from 0 remeber that
            int middleValue = nameList.Count / 2;
            //int endValue = (nameList.Count + 1);          error 
            int endValue = nameList.Count-1;
            Console.WriteLine("Enter a name to search for.");
            String name = Console.ReadLine();

            bool nameNotFound = true;
            while ((nameNotFound) && (endValue > startValue))//add end search condition
            {
                var compareResult = String.Compare(name, nameList[middleValue]);
                if (compareResult < 0)
                {
                    endValue = middleValue -1; //Substract 1
                    middleValue = endValue / 2;
                }
                else if (compareResult > 0)
                {
                    startValue = middleValue +1; //Add 1
                    middleValue = (endValue - startValue) / 2 + startValue;
                }
                else
                {
                    Console.WriteLine("Name " + name + " was found.");
                    nameNotFound = false;
                }
            }
            //consider to uncommit the line below
            //Console.WriteLine("Name " + name + " not found!"); //inform not found
            Console.ReadKey();
        }
    }
}

the code above works well.

Collectives™ on Stack Overflow

C# Binary Search returning no result

3 Answers 3

1 Comment

8 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related