이진탐색

 static void BinarySearch(List<int> datas,int findNum)
        {
            //이진탐색은 정렬된 데이터만 가능하므로 정렬.
            datas.Sort();
 
            //성능측정용
            int counter = 0;
 
            int first = 0;
            int last = datas.Count - 1;        
 
            do
            {
                counter++;
                //중앙 인덱스
                int center = (first + last) / 2;             
 
                if (datas[center] == findNum)
                {
                    Console.WriteLine(string.Format("2진 : {0} 번만에 값 찾음", counter));
                    return;
                }
                if (datas[center] > findNum)
                {
                    last = center - 1;
                }
                else
                {
                    first = center + 1;
                }                               
            }
            while (first <= last);
 
            Console.WriteLine("2진 : {0} 번을 찾아보고 값이 없다는것을 알았다.", counter);
        }
    }

List를 이용해 간단하게 binary search를 구현해 봤다.

간단하게 List의 Contains함수를 이용해 검색할 수도 있지만, Contains함수는 시간 복잡도가 O(n)이라고 한다.

물론 binary search가 훨씬 빠르긴 하지만 데이터들이 반드시 정렬이 되어 있어야 한다는 조건이 붙는다.

정렬비용과 검색비용을 고려해서 잘 사용해야 할 것 같다.

list에는 이미 BinarySearch 라는 함수가 구현이 되어 있기 때문에 굳이 구현 할 필요 없이 쓰면 될 것 같다.