[알고리즘] 이진탐색

이진 탐색

이진 탐색은 배열 내부의 데이터가 정렬되어야만 사용할 수 있는 알고리즘이다. 이러한 탐색은 O(logN)의 시간 복잡도를 갖고 있다.

해당 알고리즘의 동작 방식은 아래와 같다.
1. 배열의 중간의 것과 비교하여 해당 값쪽으로 범위를 반절 줄인다.
2. 계속해서 반복한다.
3. 중간점이 원하는 값과 일치하면 해당 함수를 종료한다.

이진 탐색을 파이썬 코드로 작성하면 다음과 같다.

def binarySearch(array, target, start, end):
    if start > end:
        return None
    else:
        mid = (start + end) // 2
        if array[mid] == target: # 해당값과 일치하는 경우
            return mid
        
        elif array[mid] > target: # 해당값이 왼쪽에 있는경우
            return binarySearch(array, target, start, mid-1)
        
        else: # 해당 값이 오른쪽에 있는 경우
            return binarySearch(array, target, mid+1, end)

반복문을 이용한 코드는 아래와 같다.

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        
        # 중간값이 해당 타겟인 경우
        if array[mid] == target:
            return array[mid]
            
         # 왼쪽에 있는 경우
        elif array[mid] > target:
            end = mid - 1
            
        # 오른쪽에 있는 경우
        else:
            start = mid + 1
    # 반복문이 다 끝난 다음에도 찾지 못한 경우
    return None