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

Edited by primzon

3
Contributors
5
Replies
32
Views
5 Years
Discussion Span
Last Post by primzon

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.

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?

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

``````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;
}
``````

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

but how to do that?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.