GWArraySearch

using System;
using System.Collections.Generic;

namespace GameWork.util {

    /**
     * @Author Alex
     */

    public class GWArraySearch {
        //vars

        //constructor
        public GWArraySearch() {

        }

        //public

        //can be used for anything, but is VERY slow
        public int linearSearch<T>(List<T> list, T search) {
            return linearSearch<T>(list.ToArray(), search);
        }
        public int linearSearch<T>(T[] arr, T search) {
            for (int i = 0; i < arr.Length; i++) {
                if (arr[i].Equals(search)) {
                    return i;
                }
            }

            return -1;
        }

        //ONLY use with sorted arrays. Very fast search
        public int binarySearch<T>(List<T> list, T search) where T : IComparable {
            return binarySearch<T>(list.ToArray(), search);
        }
        public int binarySearch<T>(T[] arr, T search) where T : IComparable {
            int min = 0;
            int N = arr.Length;
            int max = N - 1;

            do {
                int mid = (min + max) / 2;

                if (arr[mid].CompareTo(search) < 0) {
                    min = mid + 1;
                } else {
                    max = mid - 1;
                }

                if (arr[mid].Equals(search)) {
                    return mid;
                }
            } while (min <= max);

            return -1;
        }

        //ONLY use with sorted arrays. Fastest search, but experimental and only works with items that can be converted to doubles
        public int interpolationSearch<T>(List<T> list, T search) where T : IComparable, IConvertible {
            return interpolationSearch<T>(list.ToArray(), search);
        }
        public int interpolationSearch<T>(T[] arr, T search) where T : IComparable, IConvertible {
            int low = 0;
            int high = arr.Length - 1;
            int mid;

            while (arr[low].CompareTo(search) < 0 && arr[high].CompareTo(search) >= 0) {
                mid = low + (int) (((Convert.ToDouble(search) - Convert.ToDouble(arr[low])) * (high - low)) / (Convert.ToDouble(arr[high]) - Convert.ToDouble(arr[low])));

                if (arr[mid].CompareTo(search) < 0) {
                    low = mid + 1;
                } else if (arr[mid].CompareTo(search) > 0) {
                    high = mid - 1;
                } else {
                    return mid;
                }
            }

            if (arr[low].Equals(search)) {
                return low;
            }

            return -1;
        }

        //private

    }
}