이진 탐색 알고리즘으로 정렬된 배열에서 원하는 값을 찾기

이진 탐색(Binary Search) 알고리즘은 정렬된 배열에서 원하는 값을 빠르게 찾을 수 있는 알고리즘입니다. 이번 포스팅에서는 이진 탐색 알고리즘을 이용해 정렬된 배열에서 원하는 값을 찾는 예제와 풀이 과정을 살펴보겠습니다.

 

예제:
주어진 정렬된 배열에서 원하는 값 X를 찾아 인덱스를 반환하세요. 만약 값이 없으면 -1을 반환하세요.

 

예시 입력:

int[] arr = {1, 3, 5, 7, 9};
int target = 7;

 

예시 출력:

3

 

풀이 과정:

1. 시작 인덱스(start)를 0으로, 끝 인덱스(end)를 배열의 마지막 인덱스로 설정합니다.
2. 시작 인덱스가 끝 인덱스보다 작거나 같을 때까지 아래 단계를 반복합니다.
   1. 중간 인덱스(mid)를 시작 인덱스와 끝 인덱스의 평균으로 설정합니다.
   2. 배열의 중간 인덱스 값이 찾고자 하는 값과 같다면 중간 인덱스를 반환합니다.
   3. 배열의 중간 인덱스 값이 찾고자 하는 값보다 작다면 시작 인덱스를 중간 인덱스+1로 설정합니다.
   4. 배열의 중간 인덱스 값이 찾고자 하는 값보다 크다면 끝 인덱스를 중간 인덱스-1로 설정합니다.
3. 찾고자 하는 값이 없다면 -1을 반환합니다.

C# 코드 예제:

 

using System;

public class BinarySearchExample
{
    public static int BinarySearch(int[] arr, int target)
    {
        int start = 0;
        int end = arr.Length - 1;

        while (start <= end)
        {
            int mid = (start + end) / 2;

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

        return -1;
    }

    public static void Main()
    {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 7;

        int result = BinarySearch(arr, target);
        Console.WriteLine("The index of the target value is: " + result);
    }
}

 

코딩 테스트에서 이진 탐색 알고리즘은 매우 유용한 방법이니 꼭 알아두시길 바랍니다. 이번 포스팅을 통해 이진 탐색 알고리즘에 대한 이해와 정렬된 배열에서 원하는 값을 찾는 예제 및 풀이 과정을 공부하셨습니다.

다음 포스팅에서는 더 어려운 코딩 테스트 문제와 풀이 과정을 다루도록 하겠습니다. 꾸준한 연습을 통해 코딩 테스트에 대한 실력을 향상시키시길 바랍니다.