Excercism - Binary Search : 이진탐색, 이진탐색 트리

문제요약

이진탐색을 통해 찾는 숫자를 찾아 인덱스를 반환하라.

없다면 -1을 반환하라.

 

https://exercism.org/tracks/csharp/exercises/binary-search/iterations

Exercism

---

난이도

Easy

---

풀이 포인트

• Binary Search 아이디어

---

REVIEW

 

Excercism에서 푼 문제가 30여개가 넘어가다보니 느끼는 점은,

문제 구성이 참 좋다. 기본에 충실하면서도 다양한 CS 토픽이나, 흥미로운 스토리 들을 근간으로 문제를 내고 있어서 상식도 나름 쌓인다.

 

여튼 이진탐색을 또 오랜만에 풀었는데, 작동 원리가 이해는 가도 이를 코드로 옮기는 것이 아직도 힘들군 느꼈다..

또 막상 구현된 코드를 보면 정말 간단한데, 구현이 참 어렵단 말이지.

 

이런 탐색 코드는 하나쯤 외워두면 편할 것 같다.

---

CODE

using System;

public static class BinarySearch
{
    public static int Find(int[] input, int value)
    {
        // 이진 검색은 정렬된 배열에 동작.
        Array.Sort(input);

        int left = 0;
        int right = input.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2; // 중간 인덱스 계산

            if (input[mid] == value)
            {
                return mid; // 값을 찾음
            }
            else if (input[mid] < value)
            {
                left = mid + 1; // 오른쪽 절반을 탐색
            }
            else
            {
                right = mid - 1; // 왼쪽 절반을 탐색
            }
        }

        return -1;
    }
}