캐나다 IT 코딩 Binary Search

캐나다 IT 개발 구직자에게 코딩 테스트는 필수입니다. 취업, 전직 시에 코딩 테스트를 통과해야 하는 것은 분명하고 또한 개발자로서 준비하고 공부하면서 얻을 수 있는 기회입니다. 이번 글에서는 Binary Search에 대해 알아보겠습니다.

Binary Search(이진 탐색) 정의

Binary Search(이진 탐색)은 정렬된 배열 내에서 대상 값의 위치를 찾는 데 사용되는 탐색 알고리즘입니다. 대상 값을 찾거나 없음으로 판단할 때까지 탐색 간격을 반으로 계속해서 나누어 나가기 때문에 대용량의 정렬되어 있는 데이터 셋 탐색에 최적화되어 있는 탐색 방법입니다.

 

Linear Search(선형 탐색)과 Binary Search(이진 탐색) 비교

Binary Search와 Linear Search 각각 장단점이 있는 두 가지 일반적으로 사용되는 탐색 알고리즘인데 여기에서는 Binary Search를 자세히 알아보기 위한 목적으로 비교를 위해 Linear Search를 잠시 소개합니다. 그리고 참고로 앞으로는 영문 표현을 위주로 설명을 하도록 하겠습니다.

 

Linear Search(Sequential Search)

• 알고리즘: 대상 값을 찾거나 데이터 집합의 끝에 도달할 때까지 데이터 집합의 각 요소를 순차적으로 확인합니다. 
• 시간 복잡도: 데이터 집합의 크기를 나타내는 n에 대해 O(n)의 시간 복잡도를 가집니다. 선형 탐색은 데이터 집합을 선형으로 스캔하기 때문에 탐색에 소요되는 시간은 데이터 집합의 크기에 선형적으로 증가합니다. 

참고로 알고리즘의 속도를 표현하기 위해 일반적으로 Big O 표현식을 이용하는데 이에 대해서는 별도의 다른 포스팅에서 말씀드리도록 하겠습니다.

• 데이터 집합 요구 사항: 정렬되지 않은 데이터 집합과 정렬된 데이터 집합 모두에 적용할 수 있습니다. 왜냐하면 특별한 로직이 적용되는 것이 아니라 배열의 아이템 하나씩 순서대로 검색을 하기 때문입니다.
• 적합성: 데이터 집합이 작거나 정렬되지 않은 경우에 적합합니다.
• 효율성: Linear Search는 큰 정렬된 데이터 집합에 대해서는 Binary Search보다 효율적이지 않습니다. 최악의 경우에는 모든 요소를 확인해야 할 수 있기 때문입니다.

Binary Search

• 알고리즘: 탐색 구간을 절반씩 나누어 타겟 값을 찾거나 없음을 판단할 때까지 반복적으로 수행합니다.
• 시간 복잡도: 데이터셋의 크기인 n에 대해 O(log n)의 시간 복잡도를 가지며, 각 반복마다 탐색 공간을 절반으로 줄입니다.
• 데이터셋 요구사항: Binary Search 가 작동을 하기 위해서는 반드시 검색을 수행하기 위해 데이터셋이 정렬되어 있어야 합니다.
• 적합성: 효율적인 탐색이 필요한 대용량 정렬된 데이터셋에 적합합니다. (예를 들어 정렬이 되어 있는 대용량 데이터가 저장되어 있는 전화 번호부)
• 효율성: Binary Search는 로그 시간 복잡도를 가지기 때문에 대용량 정렬된 데이터셋에 대해 매우 효율적입니다. 각 반복마다 탐색 공간을 절반으로 줄여 비교해야 하는 횟수를 줄입니다.

요약하면, 작은 데이터셋이나 정렬되지 않은 데이터셋에는 Linear Search(Sequential Search)가 적합하며, 대용량 정렬된 데이터셋에는 Binary Search가 적합합니다. Binary Search는 특히 대용량 데이터셋에 대해 Linear Search에 비해 효율적인 시간 복잡도를 가지고 있습니다. 그러나 Binary Search는 데이터셋이 정렬되어야 하고, Linear Search는 정렬되지 않은 데이터셋과 정렬된 데이터셋 양쪽에서 수행할 수 있습니다.

 

Linear Search 와 Binary Search 차이점 이미지

Binary Search 와 Linear Search(Sequential Search) 의 차이점

 

Binary Search 코딩 예제

앞서 설명한 Binary Search 이론에 대한 코딩 예제를 Python으로 구성해서 보여주고 있습니다

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example usage
my_list = [1, 3, 5, 7, 9, 11, 13]
target_value = 7
result = binary_search(my_list, target_value)
print("Target value found at index:", result)

 

이 예제에서는 binary_search 함수가 정렬된 배열(arr)과 목표 값(target)을 받습니다. 이 함수는 Binary Search 알고리즘을 실행하고, 목표 값이 있다면 해당 값을 찾은 인덱스를 반환하고, 찾지 못했다면 -1을 반환합니다. 그런 다음 이 함수를 사용하여 my_list 배열에서 목표 값 7을 탐색합니다.

Binary Search의 장, 단점

장점

• 효율적: Binary Search는 O(log n)의 시간 복잡도를 가지므로, 대용량으로 정렬된 데이터셋에서 검색하는 데 매우 효율적입니다. 
• 다용도: Binary Search는 배열, 연결 리스트, 트리 등 다양한 종류의 데이터 구조에 적용할 수 있습니다.
• 검색 공간의 절반을 제거: 각 반복마다 Binary Search는 남은 검색 공간을 절반으로 줄여 비교 횟수를 감소시킵니다.

단점

• 정렬된 데이터셋이 필요합니다: Binary Search는 검색을 수행하기 위해 데이터셋이 정렬되어야 합니다. 데이터셋이 이미 정렬되어 있지 않은 경우 추가적인 전처리 단계가 필요할 수 있으며, 이는 전체적인 복잡도를 증가시킬 수 있습니다.
• 정렬된 데이터셋에만 적용 가능합니다: Binary Search는 정렬된 데이터셋에만 적용할 수 있습니다. 데이터셋이 정렬되지 않거나 지속적으로 변경되는 경우 Binary Search는 적합하지 않을 수 있습니다.
• 동적 데이터셋에 비효율적입니다: 데이터셋이 자주 업데이트되거나 수정되는 경우, Binary Search는 가장 효율적인 검색 알고리즘이 아닐 수 있습니다. 정렬된 배열에 요소를 삽입하거나 삭제하는 것은 요소들을 이동시키는 작업이 필요하며, 이는 시간과 공간 복잡도 측면에서 비용이 발생할 수 있습니다.
• 랜덤 액세스가 필요합니다: Binary Search는 데이터셋의 요소에 랜덤 액세스에 의존합니다. 링크드 리스트와 같이 효율적인 랜덤 액세스를 지원하지 않는 데이터 구조의 경우, Binary Search의 성능이 크게 감소할 수 있습니다.

코딩 테스트 실제 기출문제 - Binary Search

캐나다 IT 회사에서 출제된 Binary Search 관련 실제 기출문제를 소개합니다. 영문 자체를 한글로 굳이 번역해서 소개하지 않는 이유는 이런 패턴에 익숙해지셔야 하기 때문입니다. 그리고 Solution을 보시기 전에 반드시 우선 문제 자체를 풀어 보시고 접근하시기 바랍니다.

 

Question 1: Search Insert Position

Given a sorted array of distinct integers and a target value, write a function to return the index if the target is found. If not, return the index where it would be if it were inserted in order.

 

Example:

Input: nums = [1,3,5,6], target = 5 Output: 2

 

Solution:

def searchInsert(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return left

 

Question 2: Peak Index in a Mountain Array

Let's call an array arr a mountain if the following properties hold:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

Given an integer array arr that is guaranteed to be a mountain, return any i such that arr[0] < arr[1] < ... arr[i-1] < arr[i] > arr[i+1] > ... > arr[arr.length - 1].

 

Example:

Input: arr = [0,1,0] Output: 1

 

Solution:

def peakIndexInMountainArray(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < arr[mid + 1]:
            left = mid + 1
        else:
            right = mid

    return left

---

 

캐나다 IT 코딩 Selection Sort