이진탐색 알고리즘

소개

이진탐색 알고리즘은 정렬된 배열에서 특정 값을 찾는 데 사용되는 검색 알고리즘 중 하나입니다. 이번 글에서는 이진탐색 알고리즘을 자세히 살펴보고, C#스크립트로 예시를 작성해보겠습니다.

이진탐색 알고리즘이란?

이진탐색 알고리즘은 배열의 중간 값을 선택하여 찾고자 하는 값과 비교합니다. 만약 선택한 값이 찾고자 하는 값보다 크다면, 배열의 왼쪽 절반에 대해서 이진탐색을 반복합니다. 선택한 값이 찾고자 하는 값보다 작다면, 배열의 오른쪽 절반에 대해서 이진탐색을 반복합니다. 이 과정을 반복하여 찾고자 하는 값을 찾을 때까지 수행합니다.

이진탐색 알고리즘의 예

다음은 이진탐색 알고리즘의 예시입니다.

static int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return -1;
}

위의 예제는 정렬된 배열에서 특정 값을 찾는 이진탐색 알고리즘입니다. BinarySearch() 메서드는 배열과 찾고자 하는 값(target)을 매개 변수로 받습니다. left와 right 변수는 배열의 처음과 끝 인덱스를 가리킵니다. 이진탐색 알고리즘은 left와 right의 중간 값을 선택하여 찾고자 하는 값과 비교합니다. 만약 선택한 값이 찾고자 하는 값보다 크다면, left를 mid+1로 업데이트합니다. 선택한 값이 찾고자 하는 값보다 작다면, right를 mid-1로 업데이트합니다. 이 과정을 반복하여 찾고자 하는 값을 찾을 때까지 수행합니다.

이진탐색 알고리즘의 시간 복잡도

이진탐색 알고리즘의 시간 복잡도는 O(log n)입니다. 이는 배열의 크기가 2배씩 줄어들기 때문입니다.

결론

이진탐색 알고리즘은 정렬된 배열에서 특정 값을 찾는 데 사용되는 검색 알고리즘입니다. 이진탐색 알고리즘의 시간 복잡도는 O(log n)이며, 배열의 크기가 2배씩 줄어들기 때문입니다. 이번 글을 통해 이진탐색 알고리즘에 대해 더욱 자세히 알아보았습니다.