[알고리즘 개념정리] Binary Search (이진탐색/이분탐색)

[1] 이진탐색

* 참고서적: c언어로 쉽게 쓴 자료구조/ 생능출판 / 천인국, 공용해, 하상호 지음

* 참고자료: Leetcode Explore

 

정렬된 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이

왼쪽 또는 오른쪽 부분 리스트에 있는지를

알아내어 탐색의 범위를 반으로 줄이는 방법

 

이진탐색은 데이터의 삽입이나 삭제가 빈번할 때는 적합하지 않고

고정된 데이터에 대한 탐색에 적합하다.

 

target값이 배열의 중앙값(mid)보다 작으면=> left~ mid-1 범위만을 탐색하고

반대로, 중앙값보다 크면 mid+1~right 범위만을 탐색하면 된다.

그래서 이진탐색에 대한 시간복잡도는 O(logN) 이다. 

 

[ 이진탐색 유형 1 ]

정렬된 배열 nums에 내가 찾고자하는 target값이 있는지 확인하자.

target값이 배열 nums에 있다면, 인덱스값을 리턴하고

target값이 배열 nums에 없다면 -1을 리턴한다.

 

ex1) nums=[ -1, 0, 3, 5, 9, 12 ], target=9  => (output) 4

ex2) nums=[ -1, 0, 3, 5, 9, 12 ], target=2  => (output) -1

def Binarysearch01(nums: List[int], target: int) -> int:
	#nums는 항상 정렬된 배열이어야한다.
    nums=sorted(nums)

    left, right =0, len(nums)-1

    # 인덱스 right는 left보다 항상 크거나 같아야한다.
    while left<=right:
        # right와 left의 중간값 인덱스를 구한다.
        mid=int((left+right)//2)

        # nums[mid]가 target 과 같으면 mid값을 리턴한다.
        if nums[mid]==target:
            return mid

        # nums[mid]가 target보다 큰 경우 -> left~(mid-1)를 탐색
        elif nums[mid]>target:
            right=mid-1


        # nums[mid]가 target보다 작은 경우 -> (mid+1)~right 탐색
        else: # nums[mid]<target
            left=mid+1

    # left>right가 되어버려서
    # target은 nums배열에 존재하지 않음.
    # -1을 리턴한다.
    return -1

---

[ 이진탐색 유형 2 ]

def binarySearch02( nums: List[int], target: int) ->int:
    # nums배열의 길이가 0이라면
    if len(nums)==0:
        return -1

    # left=0, right=배열 nums의 길이  로 초기화
    left, right =0, len(nums)
    
    while left< right:
        mid= int((left+right)//2)

        # nums[mid]가 target이라면
        if nums[mid]==target:
            return mid

        # nums[mid]가 target보다 작다면 -> mid+1 ~right 범위 탐색
        elif nums[mid]<target:
            left=mid+1

        # nums[mid]가 target보다 크다면 -> left ~mid 범위 탐색
        else:
            right=mid

    # taget값이 nums에 존재하지 않으면
    return -1

---

[ 이진탐색 유형 3 ]

def binarySearch03( nums: List[int], target: int) ->int:
    # nums배열의 길이가 0이라면
    if len(nums)==0:
        return -1

    #초기화
    # left=0
    # right=배열 nums의 길이-1  
    left, right =0, len(nums)-1
    
    while left+1 < right:
        mid= int((left+right)//2)

        # nums[mid]가 target이라면
        if nums[mid]==target:
            return mid

        # nums[mid]가 target보다 작다면 -> mid ~right 범위 탐색
        elif nums[mid]<target:
            left=mid

        # nums[mid]가 target보다 크다면 -> left ~mid 범위 탐색
        else:
            right=mid

    # 마지막 확인 - target이 nums[left]/ nums[right] 와 같은지
    # target이 nums[left]와 같은가?
    if nums[left]==target: return left
    if nums[right]==target: return right
    
    # taget값이 nums에 존재하지 않으면
    return -1