Algo HW 3

// Found this method to partition an array: https://stackoverflow.com/a/1396143/6501242
public static IEnumerable<List<T>> Partition<T>(this IList<T> source, Int32 size) {
for (int i = 0; i < Math.Ceiling(source.Count / (Double)size); i++)
    yield return new List<T>(source.Skip(size * i).Take(size));
}

static bool FindViaSublist(int[] set, int target) {
    if (set.Length == 1) {
        return set[0] == target;
    }
    if (set.Length == 2) {
        return set[0] == target ? true : set[1] == target;
    }
    int sublistSize = (int)Math.Floor((double)set.Length / 3);
    IEnumerable<List<int>> partitions = Partition(new List<int>(set), sublistSize);
        partitions = partitions.Reverse();

        foreach (List<int> partition in partitions) {
            if (partition[0] < target) {
                continue;
            }
            if (partition[0] == target) {
                return true;
            }
                FindViaSublist(partition.ToArray(), target);
        }
        return false;
    }
}

// Examples:
int[] arr1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
Console.WriteLine(FindViaSublist(arr1, 5)); // True
Console.WriteLine(FindViaSublist(arr1, 100)); // False