[알고리즘] 이진탐색

이진탐색

• 정렬돼 있는 데이터에서 특정한 값을 찾아내는 알고리즘
• 이분 탐색이라고도 함
• 리스트, 트리 등의 자료구조에서 탐색하는데 사용
  • 트리 구조에서 이진탐색을 하기 위해서는 트리가 이진 탐색 트리여야 가능

  

• 원소들이 반드시 정렬되어 있어야만 사용 가능

• 처음부터 생각하기는 어렵기 때문에 쉬운 방법부터 생각

시간 복잡도

• N개의 수 정렬 : O(N * lgN)
• M개의 수 이진탐색 : O(M * lgN)
• N개의 수 정렬 후 M개의 수 이진탐색 : O((N + M) lgN)

자료 구조

• 탐색 대상 수 : int[ ]
• 탐색 하려는 수 : int[ ]

예시 코드

def search(st, en, target):
    if st == en:
        if nums[st] == target:
            print(nums[st])
        return
		
    mid = (st + en) // 2
		
    if nums[mid] < target:
        search(mid + 1, en, target)
    else:
        search(st, mid, target)