using System;
using System.Collections;
using System.Collections.Generic;
using AlgorithmCollection;
using AlgorithmCollection.Recursion;

namespace AlgorithmCollection.Searching
{

	public static class SearchingHelper
	{

		// 二分搜索，返回索引号
		// O(logn)
		public static int BinarySearch<T>(T[] dataList, T value) where T : IComparable, IEquatable<T>
		{
			int n = dataList.Length;
			int left = 0;
			int right = n - 1;
			while (left <= right)
			{
				int middle = (right + left) / 2;
				T midValue = dataList[middle];
				if (value.Equals(midValue))
					return middle;
				if (value.CompareTo(midValue) > 0)
					left = middle + 1;
				if (value.CompareTo(midValue) < 0)
					right = middle - 1;
			}
			return -1; // 没找到
		}

        public static int BinarySearch<T>(List<T> data, T value) where T : IComparable, IEquatable<T>
        {
            int index = -1;
            RecursionHelper.DivideAndConquer(
                () => 
                {
                    DivisionDescriptor div = new DivisionDescriptor();
                    div.left = 0;
                    div.right = data.Count - 1;
                    return div;
                },
                (DivisionDescriptor div) =>
                {
                    if (data[div.left].CompareTo(value) == 0)
                    {
                        index = div.left;
                    }
                },
                (DivisionDescriptor div, out bool bAdhoc) =>
                {
                    int left = div.left;
                    int right = div.right;
                    DivisionDescriptor[] division = new DivisionDescriptor[1];
                    if(right <= left)
                    {
                        division[0].left = left;
                        division[0].right = right;
                        bAdhoc = true;
                        return division;
                    }
                    int mid = (left + right) / 2;
                    T midValue = data[mid];
                    if(midValue.CompareTo(value) > 0)
                    {
                        division[0].left = left;
                        division[0].right = mid - 1;
                    }
                    else if (midValue.CompareTo(value) < 0)
                    {
                        division[0].left = mid + 1;
                        division[0].right = right;
                    }
                    else
                    {
                        division[0].left = mid;
                        division[0].right = mid;
                        bAdhoc = true;
                        return division;
                    }
                    bAdhoc = false;
                    return division;
                }
                );
            return index;
        }

		// 查找最大值
		// O(n)
		public static int FindMax<T>(IList<T> dataList) where T : IList, IComparable
		{
			int max = 0;
			for(int i = 0; i < dataList.Count; ++i)
			{
				if (dataList[i].CompareTo(dataList[max]) > 0)
					max = i;
			}
			return max;
		}

		// 查找最小值
		// O(n)
		public static int FindMin<T>(IList<T> dataList) where T : IList, IComparable
		{
			int min = 0;
			for (int i = 0; i < dataList.Count; ++i)
			{
				if (dataList[i].CompareTo(dataList[min]) < 0)
					min = i;
			}
			return min;
		}


		public static T Select_Random<T>(IList<T> data, bool descent = false) where T : IList, IComparable
		{
			return default(T);
		}

	}

}