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?

Answer 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.