[알고리즘] 이진(이분) 탐색(Binary Search)

이진 탐색(Binary Search)

이진 탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이며 이분 탐색이라고도 불린다. 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 사람들이 숫자를 맞춰가는 업다운 게임과 같은 방식이다.

참고 : 업다운 게임 - 무한도전 니가 가라 하와이편

 

 

탐색 과정

이진 탐색은 데이터가 정렬되어있는 상태에서 진행된다.

1. 시작점과 끝점 사이에 중간점을 정함
   (만일, 중간점이 실수라면 소수점 이하를 버림)
2. 중간점에 해당하는 값과 찾고자 하는 값을 비교
3. 찾고자 하는 값이 중간점에 해당하는 값보다 작다면 중간점을 기준으로 왼쪽 부분을,
   찾고자 하는 값이 중간점에 해당하는 값보다 크다면 중간점을 기준으로 오른쪽 부분에
   해당하는 데이터 범위를 가지고 1~3번 과정을 반복
4. 만일 중간점에 해당하는 값과 찾고자 하는 값이 같다면 True를 반환
5. 범위의 크기가 0이 될 때까지 계속 반복했는데도 불구하고 찾을 수 없다면 False를 반환

출처 : https://github.com/Legitcoder/Sorting

 

 

 

파이썬 코드

재귀 함수를 활용

def binary_search(arr, search):  # 재귀 함수를 활용한 ver1
    n = len(arr)
    if n == 1:
        if arr[0] == search:
            return True
        else:
            return False
    if n == 0:
        return False

    mid = n // 2

    if arr[mid] == search:
        return True
    elif arr[mid] > search:  # 중간점의 값보다 찾고자 하는 값이 작은 경우
        return binary_search(arr[:mid], search)
    else:  # 중간점의 값보다 찾고자 하는 값이 큰 경우
        return binary_search(arr[mid + 1:], search)


arr = [3, 110, 8, 13, 2]
binary_search(sorted(arr), 7)  # False 반환
binary_search(sorted(arr), 13) # True 반환

혹은

def binary_search(arr, search, start, end):  # 재귀 함수를 활용한 ver2
    if start > end:
        return False

    mid = (start + end) // 2
    if arr[mid] == search:
        return True
    elif arr[mid] > search:  # 중간점의 값보다 찾고자 하는 값이 작은 경우
        return binary_search(arr, search, start, mid - 1)
    else:  # 중간점의 값보다 찾고자 하는 값이 큰 경우
        return binary_search(arr, search, mid + 1, end)


arr = [3, 110, 8, 13, 2]
binary_search(sorted(arr), 7, 0, len(arr)-1)  # False 반환
binary_search(sorted(arr), 13, 0, len(arr)-1) # True 반환

 

 

반복문을 활용

def binary_search(arr, search):  # 반복문 활용한 ver1
    start, end = 0, len(arr) - 1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == search:
            return True
        elif arr[mid] > search:  # 중간점의 값보다 찾고자 하는 값이 작은 경우
            end = mid - 1
        else:  # 중간점의 값보다 찾고자 하는 값이 큰 경우
            start = mid + 1
    return False


arr = [3, 110, 8, 13, 2]
binary_search(sorted(arr), 7)  # False 반환
binary_search(sorted(arr), 13) # True 반환

혹은

def binary_search(arr, search, start, end):  # 반복문 활용한 ver2
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == search:
            return True
        elif arr[mid] > search:  # 중간점의 값보다 찾고자 하는 값이 작은 경우
            end = mid - 1
        else:  # 중간점의 값보다 찾고자 하는 값이 큰 경우
            start = mid + 1
    return False


arr = [3, 110, 8, 13, 2]
binary_search(sorted(arr), 7, 0, len(arr)-1)  # False 반환
binary_search(sorted(arr), 13, 0, len(arr)-1)  # True 반환

 

 

 

 

 

 

 

 

 

https://github.com/Legitcoder/Sorting

GitHub - Legitcoder/Sorting

https://library-of-k.tistory.com/3

이진탐색 ( 이분탐색, Binary Search)의 모든 것

https://hyen4110.tistory.com/m/57

[알고리즘][검색] 이진 탐색(Binary Search) - Python

https://gyoogle.dev/blog/algorithm/Binary%20Search.html

이분 탐색(Binary Search) | 👨🏻‍💻 Tech Interview