C# Recursive Binary Search

Question

I'm trying to implement a recursive binary search for this List<int>

List<int> primes = new List<int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

Console.WriteLine(RecursiveBinarySearch.FindNumber(primes, 9));
Console.WriteLine(RecursiveBinarySearch.FindNumber(primes, 12));

Here's my Recursive Binary Search

public static class RecursiveBinarySearch
    {
        public static bool FindNumber(List<int> setOfNumbers, int targetNumber)
        {
            if (setOfNumbers.Count == 0)
            {
                return false;
            }

            int midpoint = setOfNumbers.Count / 2;

            if (setOfNumbers[midpoint] == targetNumber)
            {
                return true;
            }
                
                
            if (setOfNumbers[midpoint] < targetNumber)
            {
                setOfNumbers.RemoveRange(setOfNumbers[0], midpoint);
                return FindNumber(setOfNumbers, targetNumber);
            }
            else
            {
                setOfNumbers.RemoveRange(setOfNumbers[midpoint + 1], setOfNumbers.Count - 1);
                return FindNumber(setOfNumbers, targetNumber);
            }
        }
    }

I'm getting

ArgumentException
index and count do not denote a valid range of elements in the List

in this line:

if (setOfNumbers[midpoint] < targetNumber)
            {
                setOfNumbers.RemoveRange(setOfNumbers[0], midpoint);
                return FindNumber(setOfNumbers, targetNumber);
            }

Here's a screenshot of the values of my variables in Visual Studio. https://snipboard.io/iQ6ZIc.jpg

If you have run the code or viewed the screenshot, you can see that midpoint is 2 so both arguments for RemoveRange() are valid and within range which is why I don't understand why it throws the exception.

What am I missing?

The first parameter to RemoveRange should be an index, not a number of the list. Soo instead of RemoveRange(setOfNumbers[0],...) and RemoveRange(setOfNumbers[midpoint + 1],...) try RemoveRange(0, ...) and RemoveRange(minpoint + 1, ...) — E. Shcherbo
– E. Shcherbo, Commented Apr 11, 2022 at 11:50
Also notice that the second parameter is how many elements you want to remove. So RemoveRange(midPoint + 1, count - 1) will also fail, because you want to remove the half of the elements, not count - 1 elements. — E. Shcherbo
– E. Shcherbo, Commented Apr 11, 2022 at 11:53
See the spec for details learn.microsoft.com/en-us/dotnet/api/… — E. Shcherbo
– E. Shcherbo, Commented Apr 11, 2022 at 11:56
Is this for educational purposes or something you would actually use in your app? Using RemoveRange would make it very slow. — Magnus
– Magnus, Commented Apr 11, 2022 at 11:57
public static bool FindNumber(List<int> setOfNumbers, int targetNumber) => setOfNumbers.BinarySearch(targetNumber) >= 0 — Magnus
– Magnus, Commented Apr 11, 2022 at 12:03

JonasH · Accepted Answer · 2022-04-11 13:03:54Z

1

You probably do not want to implement a search method that works by removing items. That will probably be much slower than just doing a linear search. It also modified the original collection, and that is typically not what you would expect from a method named FindNumber. You probably want to use a method that takes a specified range to search in as an argument. For example:

public static bool FindNumber(List<int> setOfNumbers, int targetNumber)
    => FindNumber(setOfNumbers, targetNumber, 0, targetNumber.Count);

private static bool FindNumber(List<int> setOfNumbers, int targetNumber, int startIndex, int count){

    int midpoint = startIndex + count / 2;
    var endIndex = startIndex + count;

   ...
    // Search lower range
    return FindNumber(setOfNumbers, targetNumber, startIndex, midpoint  - startIndex);
   ...
   // Search upper range
   return FindNumber(setOfNumbers, targetNumber, midpoint , endIndex - midpoint );
}

You might also consider returning the index of the found number, or just use the existing implementation of BinarySearch.

You might also consider changing your input type to something like IReadOnlyList<int> or Span<int> to accept any kind of sequential list, and also to accept generic types with a IComparer<T> parameter to do the comparison, using Comparer<T>.Default as the default value if no explicit comparer is used.

edited Apr 11, 2022 at 13:03

answered Apr 11, 2022 at 12:45

JonasH

38.5k2 gold badges16 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Magnus Over a year ago

Or maybe a Span<int>

Cedd Over a year ago

Thanks JonasH. Learned something new :)

Collectives™ on Stack Overflow

C# Recursive Binary Search

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related