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

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; // 没找到
        }

    }

}