Bisection method problem

[primzon]

Hi there!

Maybe anyone know how to solve this problem?
First of all, here is a code:

static void Main(string[] args)
        {
            int[] array = { 25, 47, 47, 55, 59, 69, 72, 89, 93, 117 };
            int element = 47;

            int index = findWithBisection(element, array);
            Console.WriteLine("Element " + element + " is one the place: " + index);
        }

static int findWithBisection(int el, int[] a)
        {
            if (a.Length == 0)
            {
                return -1;
            }

            if (a != null)
            {
                int right = a.Length - 1; // right searching zone 
                int left = 0;   // left searching zone
                int half;   // index of halved array

                while (left <= right)
                {
                    half = (left + right) / 2; 
                    while (left <= half)
                    {
                        if (a[left] != el)
                            left++;
                        else
                            return left;
                    }

                    if (a[half] == el)
                        return half;

                    else if (a[half] < el)
                    {
                        left = half + 1;
                    }
                    else
                    {
                        right = half - 1;
                    }
                }
            }
            return -1;
        }

With this code I get result: Element 47 is on the place: 1
But we have two 47 numbers in array so currently code is searching FIRST repeating of element.
And I need to find LAST repeating of element
So in this case, the result should be: Element 47 is on the place: 2 (cuz thats the last repeating of element in array). How to change the code then?

Any suggestion is the most welcome!

Best regards,
Tr1umPr0

[gusano79]

Nitpick: The bisection method is something else.

This looks like it wants to be a binary search, but then it does a linear search on half of the array... strange. Is this a home-grown search algorithm, or is it a specific assignment?

Notice that the array is sorted, so repeated values will be next to each other. Once you've found the value, just keep shifting right as long as it's the same value. Not super efficient, but it'll get you there.

[Ketsuekiame]

You return as soon as you find your element. You need to keep searching...

Declare a new variable local to your bisection method and store in there the last index you scanned. Iterate until the values are greater than your element, each time you find your element, replace the last index value with the current one in your local variable. Once you're done, return that.

It looks like you're trying to implement a binary search. Which, if you are, is being done incorrectly. Is this what you're trying to do?

[primzon]

Yes, i did exactly what you just said (keep shifting right as long as its the same value) but if we have array with all the same values i get error. Example: { 5, 5, 5, 5, 5, 5 }. => Error

code which i made was:

static int findWithBisection(int el, int[] a)
        {
            if (a.Length == 0)
            {
                return -1;
            }

            if (a != null)
            {
                int right = a.Length - 1; 
                int left = 0;
                int half;

                while (left <= right)
                {
                    half = (left + right) / 2;
                    while (left <= half)
                    {
                        if (a[left] == el)
                        {
                            if (a[left] != (a[left + 1]))
                            {
                                return left;
                            }
                            else
                            {
                                left++;
                            }
                        }
                        else
                            left++;
                    }

                    if (a[half] == el)
                    {
                        if (a[half] != (a[half + 1]))
                        {
                            return half;
                        }
                        else
                            half++;
                    }

                    else if (a[half] < el)
                    {
                        left = half + 1;
                    }
                    else
                    {
                        right = half - 1;
                    }
                }
            }
            return -1;
        }

[Ketsuekiame]

You just need to make sure your index is lower array count - 1. Once it reaches the number of items in your array, return.

[primzon]

but how to do that?