Binary Search(이진 탐색)

이진 탐색이란 범위를 반씩 좁혀가는 탐색을 말한다. (전처리 과정으로 정렬이 필요하다)

 

※ 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 쉽지만 오래 걸림 (최악의 경우 시간 복잡도: O(N))

 

• 필요 변수 3개 - (각 범위의) 시작점, 중간점, 끝점(의 index)
• 방법: 찾으려는 데이터와 중간점에 있는 데이터를 반복적으로 비교

    ① 찾으려는 데이터와 중간점에 있는 데이터의 값이 같을 경우: return

찾으려는 데이터와 중간점에 있는 데이터가 같을 경우

 

    ② 찾으려는 데이터가 중간점에 있는 데이터보다 작을 경우(찾.데<중.데):

                                                                             중간점을 기준으로 중간점보다 작은 곳에 있는 데이터 탐색

찾으려는 데이터가 중간점에 있는 데이터보다 작을 경우

 

    ③ 찾으려는 데이터가 중간점에 있는 데이터보다 클 경우(찾.데>중.데):

                                                                             중간점을 기준으로 중간점보다 큰 곳에 있는 데이터 탐색

찾으려는 데이터가 중간점에 있는 데이터보다 클 경우

• 시간 복잡도: O(logN)
• 구현 방법 - 재귀 함수, 반복문

 

 

※ 이진 탐색 트리

왼쪽 자식 노드<부모 노드 <오른쪽 자식 노드의 특징을 가진 이진트리

먼저 루트 노드를 방문하고 조건에 따라 ①return 할지, ②왼쪽 노드를 방문할지, ③오른쪽 노드를 방문할지가 결정됨

이진탐색트리 간략화

"이것이 취업을 위한 코딩테스트다 with 파이썬(나동빈 저)"를 보고 정리한 내용

출처| 이것이 취업을 위한 코딩테스트다 with 파이썬(나동빈 저)