[Unity C#] 이진 탐색(Binary Search)

개념

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

과정

오름차순으로 정렬된 배열이 있다.

{ 17, 28, 43, 67, 88, 92, 100 }

이 배열에서 이진 탐색을 이용하여 43의 값을 찾아보자.

 

첫 번째 시도

우선 가운데에 위치한 임의의 값 67을 선택한다.

선택한 값 67과 찾고자 하는 값 43를 비교한다.

43 < 67 이므로 43은 67의 좌측에 존재한다는 것을 알 수 있다.

 

두 번째 시도

67을 기준으로 좌측에 있는 배열 값들을 대상으로 다시 탐색을 진행한다.

{ 17, 28, 43 }

마찬가지로 가운데의 임의의 값 28을 선택한다.

28 < 43 이번에는 28이 43보다 작으므로 28 우측에 위치하는 것을 알 수 있다.

 

세 번째 시도

28의 우측을 기준으로 배열을 다시 설정해보면

{ 43 }

배열에 값이 하나만 남게 되고 값을 확인해보면,
43 == 43 원하는 값을 찾았다.

 

장점

처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠른 장점을 지님

시간복잡도 전체 탐색 : O(N) 이분 탐색 : O(logN)

 

소스코드

using System.Collections;
using System.Collections.Generic;
using System;
using UnityEngine;

public class BinarySearch_Source : MonoBehaviour
{
    // Start is called before the first frame update
    void Start()
    {
        int[] arr = new int[10] { 8, 2, 5, 4, 3, 9, 1, 6, 10, 7 };

        Array.Sort(arr);// 1 2 3 4 5 6 7 8 9 10
        //Debug.Log(BinarySearch(arr, 9));
        Debug.Log(BinarySearch_Recursive(arr, 9 , 0 , arr.Length-1));
    }

    /*
    int BinarySearch(int[] arr, int target)
    {
        Array.Sort(arr);// 1 2 3 4 5 6 7 8 9 10

        int start = 0;
        int end = arr.Length - 1;
        int mid;

        while (start <= end)
        {
            mid = (start + end) / 2;
            Debug.Log("start : " + start + " end : " + end);
            if (arr[mid] == target)
                return mid;
            else if (arr[mid] > target)
                end = mid - 1;
            else 
                start = mid + 1;
        }
        return -1;
    }*/
    //iterate 1
    //arr[4] = 5 target = 9이므로 start = mid+1 즉, start:5 end:9
    //iterate 2
    //arr[7] = 8 target = 9이므로 start = mid+1 즉, start:8 end:9
    //arr[8] == target 이므로 8번째에 있다

    int BinarySearch_Recursive(int[] arr, int target , int start, int end)
    {
        if (start > end)
            return -1;

        int mid = (start + end) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target) // target이 중앙값보다 작으므로 왼쪽에 있다
            return BinarySearch_Recursive(arr, target, start, mid - 1);
        else
            return BinarySearch_Recursive(arr, target, mid + 1, end);
        

    }

}