Post #7 Implementation of binary search in the language

Binary Searches VS Other Searches: I feel like it's important to really explain Binary Searches VS Other Searches.

Other Searches: When you think of searching you think of typing in the word "apple" into google. When you run a search in a program normally it will be a run through search. By that I mean if your trying to get the number 5 from an array of the integers 0-9 it will see 1 2 3 4 5 and stop at 5. If your looking at the alphabet trying to get Z, your program reads A B C D E F G H I J K L M N O P Q R S T U V W X Y Z and then stops because it found Z. Now imagine your looking for the number 999999999 in an array from 0-1000000000. Now your search will give you all the numbers up to that. If I wrote that out you guys would probably be bored around 100 and would not like me by 1000000 so just imagine it. That is the most basic way of searching also the most complicated. You can also have reverse searching where it starts at the end but you run into the same problem. An array count down from 10 looking for 0 will have 10 9 8 7 6 5 4 3 2 1 0. A larger example would be 1000000 looking for 10. Again just imagine that. The third way of normal searching is just completely random. Even on a small scale this can be painful. Guessing a number that someone picked between 1-10. A human won't repeat so let's say the number is 6 so the other person guesses 5 2 7 6. Well that was simple now let's show a computer guessing a number from 1-10 so same number and 3 4 8 4 3 9 1 0 5 7 8 4 9 4 8 6. Obviously the computer takes more time to find it even if you do tell it not to guess the same number it still occasionally is the random number you just don't see it. Now let me stop torturing you and tell you about the simple way of searching.

Binary Searches: Binary Searching takes yes or no responses. When you write a program which I will have under this explanation, its asking questions. It is based on three numbers a max(top), min(bottom), and mid(middle). It starts with a whole array but then cuts it in half based on the answer. This array can be numbers in order least to greatest, an alphabetical ordered list, or even any list but that changes how you find your answer. Lets start with the numbers in order. You don't actually need an array because max and min become your list of numbers. Let's use the example for above. Guessing a number 1-10 and let's say the answer is 6. Top is 10, bottom is 1, middle is (10 + 1) / 2 which is 11 / 2 which is 5 or 6 depending on the program. Let's say 5 because C# rounds 5.5 down to 5. Anyway the first time through "is the number greater than or less than  or equal to 5?", greater so bottom is now 5, top stays 10, middle is 7.5 rounded down 7. Second round, less than so bottom is still 5, top is now 7, middle is 6. Third round middle is 6 and answer is 6 so program shuts down. That was 3 steps to find the number instead of more steps to find the number. The goal of binary searches is to find the answer faster by decreasing the possibilities by half each time. Let's try an A-Z example looking for Z like above. Normally that would mean the whole alphabet unless you go in reverse. Well here there's 6 steps, first top is Z, bottom is A, middle is M. Top is Z, bottom is M, middle is S. Top is Z, bottom is S, middle is V. Top is Z, bottom is V, middle X. Top is Z, bottom is X, Middle is Y. Middle is Z program ends. That's a lot going on but a computer could have 100 more guesses and almost all duplicates. That was only 6 steps. You may be wondering how you handle a list, well if its not ordered numbers and not alphabetical and just random words or letters, you can do the same as I did above but with the index or placements in the list. Now for an example to show you what I mean. This finds the number 20 in the list of numbers 0 to 100. As I said C# rounds anything .5 down to the lower number. 

using System;

namespace BinarySearch

{

    class Program

    {

        static void Main(string[] args)

        {

            int bottom = 0;

            int top = 100;

            int middle = top + bottom;

            middle /= 2;

            int num = 20;

            Console.WriteLine("bottom: " + bottom);

            Console.WriteLine("middle: " + middle);

            Console.WriteLine("top: " + top);

            Console.WriteLine();

            while(middle != num){

                if(num < middle){

                    top = middle;

                    middle = top + bottom;

                    middle /= 2;

                    Console.WriteLine("bottom: " + bottom);

                    Console.WriteLine("middle: " + middle);

                    Console.WriteLine("top: " + top);

                    Console.WriteLine();

                }else if(num > middle){

                    bottom = middle;

                    middle = top + bottom;

                    middle /= 2;

                    Console.WriteLine("bottom: " + bottom);

                    Console.WriteLine("middle: " + middle);

                    Console.WriteLine("top: " + top);

                    Console.WriteLine();

                }

            }

            if(middle == num){

                Console.WriteLine("number was " + middle);

            }

        }

    }

}

I'm not going to bother explaining the code because if you don't understand this you

obviously haven't been reading this blog and somehow missed these lines of code from

other programming languages. Basically variables, prints, while loop, if statements,

etc. Only thing I will say /= is divide equals which we don't use much but is in here.

Expected output should be

bottom: 0 middle: 50 top: 100 bottom: 0 middle: 25 top: 50 bottom: 0 middle: 12 top: 25 bottom: 12 middle: 18 top: 25 bottom: 18 middle: 21 top: 25 bottom: 18 middle: 19 top: 21 bottom: 19 middle: 20 top: 21 number was 20

This is the end of this post.

I used the book The C# Programming Language Fourth Edition By Anders Hejlsberg, Mads

Torgersen, Scott Wiltamuth, and Peter Golde for information in this post.

Resources: Same Resources

MICROSOFT VISUAL C# .NET by Mickey Williams
PROGRAMMING BASICS FOR ABSOLUTE BEGINNERS by NATHAN CLARK
The C# Programming Language Fourth Edition by Anders Hejlsberg, Mads Torgusen,
Scott Wiltamuth and Peter Golde

Visual Studio Code Environment:

Link to get started:

https://docs.microsoft.com/en-us/dotnet/core/tutorials/with-visual-studio-code#hello-world