이분 탐색 알고리즘

이분 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾는 알고리즘으로, 탐색 범위를 반으로 나누어 중간값을 비교하여 원하는 값이 왼쪽에 있는지 오른쪽에 있는지 판단하는 방식입니다. 

이분 탐색의 구현 방법은 다음과 같습니다.

1. 배열의 중간값을 찾습니다.
2. 중간값과 찾으려는 값과 비교합니다.
3. 중간값이 찾으려는 값과 같다면 탐색을 종료합니다.
4. 중간값이 찾으려는 값보다 크다면, 배열의 왼쪽 절반에 대해서 이분 탐색을 수행합니다.
5. 중간값이 찾으려는 값보다 작다면, 배열의 오른쪽 절반에 대해서 이분 탐색을 수행합니다.
6. 배열의 크기가 0이 될 때까지 1~5번 과정을 반복합니다.

C#으로 구현한 이분 탐색 예시

 

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

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

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

    return -1; // 탐색 실패
}

 

Java로 구현한 이분 탐색 예시

 

int binarySearch(int[] arr, int target, int size) {
    int left = 0;
    int right = size - 1;

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

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

    return -1; // 탐색 실패
}