none
Find number in array with bisection. c#

    Question

  • I would  like to know how to do this with bisection. 

    I need to find element in array with bisection and output its index to console.

    Element I wan't to find: 2

    example array: -1 , 0, 1, 2, 2, 3 

    output to console(index of that  last element with value 2 in array): 4

    public void Main()
        {
            int elementToFind = 2;
            int[] arrray = { -1, 0, 1, 2, 2, 3 };
        }
    public static int findNumber(int el, int[] a)
            {
                if (a == null || a.Length == 0)
                    return -1;
    
                int left = 0;
                int right = a.Length - 1;
    
                while (left <= right)
                {
                    int middle = left + (right - left) / 2;
    
                    if (a[middle] > el)
                    {
                        right = middle - 1;
                    }
                    else if (a[middle] < el)
                    {
                        left = middle + 1;
                    }
                    else
                    {
                        return middle;
                    }
                }
                return -1;
            }

    I got this code so far but it returns element that I'm searching at random position :\



    Sunday, April 2, 2017 8:12 AM

All replies

  • I would  like to know how to do this with bisection. 

    I need to find element in array with bisection and output its index to console.

    Element I wan't to find: 2

    example array: -1 , 0, 1, 2, 2, 3 

    output to console(index of that  last element with value 2 in array): 4

    public void Main()
        {
            int elementToFind = 2;
            int[] arrray = { -1, 0, 1, 2, 2, 3 };
        }


    Hi,

    here are two ways (the first is kind of a lazy way...): Both are not bisetion but in the other thread I think everything is already answered... [ https://social.msdn.microsoft.com/Forums/office/en-US/fabcae72-11d2-4ea4-9e52-363acf06013d/find-number-in-array-with-bisection?forum=csharpgeneral ]

                int elementToFind = 2;
                int[] arrray = { -1, 0, 1, 2, 2, 3 };
    
                Console.WriteLine(arrray.ToList().LastIndexOf(elementToFind));
                Console.WriteLine(Array.LastIndexOf(arrray, elementToFind));

    Btw: What do you mean with "bisection". I understand you that way, that you want to repeatedly split the array in two and look in which half the number to search for is...  (do you need to write the algorithm yourself?)

    Regards,

      Thorsten


    Sunday, April 2, 2017 9:00 AM
  • I need to write algorithm myself :P And yes in this way of repeatedly split the array in two and look in which half the number to search for is..
    Sunday, April 2, 2017 9:17 AM

  • I got this code so far but it returns element that I'm searching at random position :\



    It will return the first position it finds the number, which a binarysearch does IMHO.

    You could easily extend it to return the last position, use a second while loop as a kind of a lazy way...

            public static int findNumber2(int el, int[] a)
            {
                if (a == null || a.Length == 0)
                    return -1;
    
                int left = 0;
                int right = a.Length - 1;
    
                while (left <= right)
                {
                    int middle = left + (right - left) / 2;
    
                    if (a[middle] > el)
                    {
                        right = middle - 1;
                    }
                    else if (a[middle] < el)
                    {
                        left = middle + 1;
                    }
                    else
                    {
                        while (middle + 1 < a.Length && a[middle + 1] == a[middle])
                            middle++;
    
                        return middle;
                    }
                }
                return -1;
            }

    Regards,

      Thorsten


    Sunday, April 2, 2017 9:33 AM
  • This example works as expected:

       int elementToFind = 2;

       int[] arrray = { -1, 0, 1, 2, 2, 3 };

       var index = findNumber( elementToFind, arrray );

       Console.WriteLine( index );

    It displays 4 according to requirement. Do you have an example that does not work?

    Sunday, April 2, 2017 9:35 AM

  • It displays 4 according to requirement. Do you have an example that does not work?

    Hi, add a third 2 to the array. (Which also shows that ritehere34 is correct about the BinarySearch which will not work in every case)

    { -1, 0, 1, 2, 2, 2, 3 }

    Regards,

      Thorsten

    Sunday, April 2, 2017 9:36 AM