Loading

How do i prevent stack overflows in binary search algorithm?

How do i prevent stack overflows in binary search algorithm?

Alex M

7y2.3kVisual Basic .NET

I'm using the following c# binary search algorithm to search for doubles in a double array containing 256 - 4096 elements:

public static void Search(double[] array, double key)
{
Quicksort.Sort(array);
int min = 0;
int max = array.Length - 1;
bool found = false;
while (min <= max)
{
int mid = (min + max) / 2;
if (array[mid] == key)
{
found = true;
Console.WriteLine($"{key} was found at index {mid} of the array");
}
else if (array[mid] > key)
max = mid - 1;
else if (array[mid] < key)
min = mid + 1;
}
if (found == false)
Console.WriteLine($"{key} wasn't found in the array.");

When i try to run it, i get a stack overflow exception thrown... How do i fix it?

Thanks for the help!

2 Replies

Know the answer? Post it — somebody with the same question will find it here.

Manoj Bhoir7y ago
Accepted answer
Hi Alex,

As per your code in QuickSort.cs inside Sort method check below code
Sort(a, start, j);
Sort(a, j + 1, end);
I found that when start = 0 and end = 0 your code goes in infinite loop due to which you are getting StackOverflow Exception.
Just check your loop coditions properly.

Quick Fix :
if (start != 0 && end != 0)
{
     Sort(a, start, j);
     Sort(a, j + 1, end);
}
0
Amit Kumar7y ago
Hi,
I think which logic you are implementing it is not a binarbinary search.

Binary Search : First you'll have to sort an array In asc or desc. After that array mid index Value (array.length/2 which index you will get now find the Value of Value of this from your array). Now match this Value from those Value which you want to search if your searcsearch Value is less than from mid index Value then search Value from 0 Index to mid index otherwise search it from mid index to last index of an array. It is called binary search.I hope this will help you.
0