3.3. Search - 3.3.1 Binary Search

CS - 3. Common Algorithms - 3.3. Search - 3.3.1 Binary Search

 

 

Search Algorithms

💡 Search algorithms are used to find a specific item in a collection of items. For example, if you have a list of names and you want to find a specific name, you can use a search algorithm to find that name.

검색 알고리즘은 항목 모음에서 특정 항목을 찾는 데 사용됩니다. 예를 들어, 이름 목록이 있는데 특정 이름을 찾으려는 경우 검색 알고리즘을 사용하여 해당 이름을 찾을 수 있습니다.

 

 

 

Binary Search

💡 Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

이진 검색은 정렬된 배열 내에서 대상 값의 위치를 찾는 검색 알고리즘입니다. 이진 검색은 대상 값과 배열의 중간 요소를 비교합니다. 둘이 같지 않으면 목표값이 놓일 수 없는 절반을 제거하고 나머지 절반에서 검색을 계속하여 다시 중간 요소를 목표값과 비교하고 목표값을 찾을 때까지 이 과정을 반복합니다. 나머지 절반이 비어 있는 상태에서 검색이 끝나면 대상이 배열에 없는 것입니다.

 

Binary Search(이진탐색)은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.

이 알고리즘은 배열의 중간 요소와 찾고자 하는 값을 비교하여 탐색 범위를 반으로 줄여나가는 방식으로 동작합니다.

이해를 돕기 위한 간단한 예시를 보여드리겠습니다.

 

예시로

배열 [1,3,5,7,9,11,13,15] 에서 숫자 9 를 찾는다고 가정해 봅시다.

Binary Search는 이러한 과정을 거칩니다.

1. 배열의 가운데 요소인 7과 찾고자 하는 값 9를 비교합니다.

2. 7은 9보다 작기 때문에, 7 왼쪽에 위치한 값들은 9보다 작다고 판단합니다.

따라서 7을 포함한 왼쪽부분은 탐색 범위에서 제외합니다.

3. 남은 배열은 [9, 11, 13, 15] 입니다. 이제 다시 중간 요소 11과 9를 비교합니다.

4. 11은 9보다 크기 떄문에, 11 오른쪽에 위치한 값들은 9보다 크다는 것을 알 수 있습니다.

따라서 11을 포함한 오른 쪽 부분 배열은 탐색 범위에서 제외합니다.

5. 남은 배열은 [9,] 입니다. 따라서 중간요소인 9와 찾고자 하는 대상 9가 일치하므로 원하는 값을 찾았습니다.

 

추리게임류에서 여러 구슬중 하나만 다를때 양팔 저울을 최소 횟수로 사용해서 구할때 사용하는 논리와 비슷하게 전개됩니다.

 

탐색 범위를 반으로 줄여가므로, Binary Search는 대상을 빠르게 찾을 수 있는 효율적인 알고리즘입니다.

 

In 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

 

위의 예시에서 arr은 정렬된 배열이며, target은 찾고자 하는 값입니다.

low, high, mid는 각각 탐색 범위의 시작, 끝, 중간 입니다.

위에서 말했던 대로 target 값을 mid(중간)을 비교하고 +-1 을 하며 탐색합니다.

함수는 찾고자 하는 값의 인덱스를 반환하며, 만약 값이 배열에 없을 경우 -1을 반환합니다.

 

Binary Search는 특성상 탐색 대상이 정렬된상태여야만 사용할 수 있습니다.

이를 위해 미리 배열을 정렬해야 합니다.

시간복잡도는 O(log n)으로 매우 효율적이기 때문에, 크기가 큰 정렬된 배열에서 원하는 값을 빠르게 찾을때 활용하기 좋습니다.

 

(사전에서 단어를 찾는경우, DB에서 특정 레코드를 찾는 경우등등)