Testing Dichotomy

Dichotomy.csx

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

static int SearchWithDichotomy(IList<int> nums, int target)
{
    var min = 0;
    var max = nums.Count;

    while (min <= max)
    {
        var middle = (min + max) / 2;
        if (middle >= nums.Count)
            break;
        var v = nums[middle];
        if (v == target)
            return middle;
        if (target < v)
            max = middle - 1;
        else
            min = middle + 1;
    }

    return -1;
}

static int SearchWithDichotomyRecursive(IList<int> nums, int target, int min, int max)
{
    var middle = (min + max) / 2;
    if (middle >= nums.Count)
        return -1;
    if (min == max)
        return min;
    if (nums[middle] == target)
        return middle;
    if (nums[middle] > target)
        return SearchWithDichotomyRecursive(nums, target, min, middle - 1);
    return SearchWithDichotomyRecursive(nums, target, middle + 1, max);
}

var nums1 = Enumerable.Range(1, 100000).ToList();

var i1 = SearchWithDichotomy(nums1, 2);
var i2 = SearchWithDichotomy(nums1, 102);
var i3 = SearchWithDichotomy(nums1, 621);
var i4 = SearchWithDichotomy(nums1, 999);
var i5 = SearchWithDichotomy(nums1, 100005);

Console.WriteLine($"i4: {i4}");

// build with optimizations to avoid stack overflow :)
var j1 = SearchWithDichotomyRecursive(nums1, 2, 0, nums1.Count);
var j2 = SearchWithDichotomyRecursive(nums1, 102, 0, nums1.Count);
var j3 = SearchWithDichotomyRecursive(nums1, 621, 0, nums1.Count);
var j4 = SearchWithDichotomyRecursive(nums1, 999, 0, nums1.Count);
var j5 = SearchWithDichotomyRecursive(nums1, 100005, 0, nums1.Count);

Console.WriteLine($"j4: {j4}");

Optimization with 64 bits avoids stack overflow for recursive version.

FSharp tail recursion is better 😃

Hello,

I think there is an error on the dichotomy by recursion ==> implying the Stack Overflow. You should use the value middle for the lower or upper bound.

 static int SearchWithDichotomyRecursive(IList<int> nums, int target, int min, int max)
        {
            var **middle** = (min + max) / 2;
            if (middle >= nums.Count)
                return -1;
            if (min == max)
                return min;
            if (nums[middle] == target)
                return middle;
            if (nums[middle] > target)
                return SearchWithDichotomyRecursive(nums, target, min, **middle** - 1);
            return SearchWithDichotomyRecursive(nums, target, **middle** + 1, max);
        }

Ho shit you are right !
I used a wrong variable 😃