C# Binary Search of a number in an array using recursion

Recursion works by breaking the entire problem into smaller parts. If you are at the smallest part (meaning that your array has only one value) then you would have your solution. This would also be your first case that you have to handle.

if (arr.Length == 1) return arr[0];

Now you can start to break down the problem. Binary left or right decision. As you already wrote you want to check weather the number is left or right from the middle of your array. So in your condition you need to access the element in the array using the [ ] operator:

if (ind > arr[arr.Length / 2]) // check if larger than the middle element

To extract a part of the array you need a second array in which you can copy the content that you want. Since you intend to pass only half of the current array into the recursive call you also need only half of the size.

int [] temp = new int[arr.Length / 2];

Now you can copy the part that you desire (first or second) depending on your condition and keep searching with a recursive call.

To copy the Array you can use the Arra.Copy method. You can pass the start and length to this method and it will copy the left or the right part into the int [] temp array. Here is an example of how to copy the right part:

Array.Copy(arr, arr.Length / 2, temp, 0, arr.Length / 2);

In the end you will need to fire your recursive call. This call will expect the new array and still the same number to look for. So since you copied either the left or right half of the previous array, now you pass the new short array to the recursive call:

return arrayIndexValue(temp, ind);

And there you have it

So the problem you have right now is that you haven't broken your problem into repeating steps. It actually should be very similar flow to a loop without all the variables. I want to do something a little simpler first.

void int find(int[] values, int at, int value) {
    if (values.Length >= at || at < 0) {
        return -1;
    } else if (values[at] == value) {
        return at;
    }
    return find(values, at+1, value);
}

This function just moves a index up one every time via recursion, but we can also do something very similar with a loop.

void int find(int[] values, int at, int value) {
    while (values.Length < at && at >= 0) {
        if (values[at] == value) {
            return at;
        }
        at = at + 1;
    }
    return -1;
}

The whole reason we usually talk about recursion is that it is usually used so that you have no "mutating" state. The variables and there values are the same for every value. You can break this, but it is usually considered beneficial. A quick stab at your problem produces something like

void int find(int[] sortedValues, int start, int end, int value) {
    var midIndex = (start + end) / 2;
    var mid = sortedValues[midIndex];
    if (start == end) {
        return mid == value ? midIndex : -1;
    } else if (mid > value) {
        return find(sortedValues, mid, end, value);
    } else if (mid < value) {
        return find(sortedValues, start, mid, value);
    } else {
        return midIndex;
    }
}

However, this isn't perfect. It has known issues like edge cases that would cause a crash. It should definitely be cleaned up a little. If you want to really want to dip your toe into recursion, try a purely functional language where you cannot mutate, like Haskell, Elm, or maybe something a little impure like F#, Clojure, or Scala. Anyway have fun.

Recursive Binary search using C# 12 in .NET 8.

I'm using Range operator introduced in C# 8 here. And using NUnit 3 for testing.

public static int BinarySearcher(int[] sortedItems, int item)
{
    // Base case
    if (sortedItems.Length == 0) return -1;
    
    var midIndex = sortedItems.Length / 2;
    var guess = sortedItems[midIndex];

    if (guess == item) return midIndex;
    
    // Recursive cases
    // 1. Throw away the right half and search again
    if (guess > item)
    {
        var leftHalf = sortedItems[..midIndex]; // Upper index is not included, so it has elements from start to midIndex - 1
        return BinarySearcher(leftHalf, item);
    }
    
    // 2. Throw away the left half and search again
    var rightHalf = sortedItems[(midIndex + 1)..];
    var result = BinarySearcher(rightHalf, item);
    // The returned index should be offset by midIndex + 1 for right half search
    return result == -1 ? -1 : midIndex + 1 + result;
}

And test it like:

using NUnit.Framework;

public class DivideAndConquerTests
{
    [Test]
    public void BinarySearcher_Finds_Item_Using_DAndC()
    {
        // Arrange
        int[] myList = [1, 3, 5, 7, 9];
        var myListItem = myList[3];
        // Act
        var searchedItemIndex = BinarySearcher(myList, myListItem);
        // Assert
        Assert.That(searchedItemIndex, Is.EqualTo(3));
    }

    [Test]
    public void BinarySearcher_Doesnt_Find_Item_Using_DAndC()
    {
        // Arrange
        int[] myList = [1, 3, 5, 7, 9];
        // Act
        var searchedItemIndex = BinarySearcher(myList, 10);
        // Assert
        Assert.That(searchedItemIndex, Is.EqualTo(-1));
    }
}