이진 탐색

순차 탐색

- 가장 기본적인 탐색 방법

- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법.

- 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용

- 시간만 충분하다면 항상 데이터를 탐색할 수 있다.

- 최악의 경우 복잡도는 O(N)

 

# count() 메소드는 내부에서 순차탐색을 수행한다.

 

이진 탐색

- 리스트 내부의 데이터가 정렬되어 있을 때만 사용할 수 있다.

- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기 때문에 매우 빠르게 수행된다.

- 시작점, 끝점, 중간점 3개를 가지고 리스트를 탐색하는데 찾고자 하는 데이터와 중간점에 있는 데이터와 비교하며 탐색한다.

- 한 번 확인할 때마다 확인하는 원소의 개수가 절반으로 줄어들어서 시간 복잡도는 O(logN)

* 처리해야 할 데이터의 수나 값이 1000만 단위 이상으로 넘어가면 이진탐색과 같은 O(logN)의 속도를 내는 알고리즘을 사용해야 한다.

 

반복문으로 작성한 이진 탐색 코드 with Python

def binarySearch(array, target, start, end):
    while start <= end:
        mid = (end + start) // 2

        if array[mid] == target:
            return True
        if array[mid] > target:
            end = mid - 1
        else:
            start = mid+1
    return None

- array는 탐색할 리스트

- target은 찾고자 하는 데이터

- start는 시작점, end는 끝점.

 

이진 탐색 트리

- 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료 구조

- 부모 노드보다 왼쪽 노드가 작고 오른쪽 노드가 크다.

 

 

이진 탐색을 적용해야 하는 문제는 입력이 많기 때문에 파이썬에서 입력을 받을 때 input()메소드를 사용하면 시간초과가 발생할 수 있다.

이때 sys 라이브러리의 readline함수를 이용하면 빠르게 입력을 받을 수 있다.

import sys

input = sys.stdin.readline().rstrip()

 

이것이 취업을 위한 코딩 테스트다 with 파이썬 185-205p