Binary Search

이진 탐색 알고리즘 : 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘

 

순차 탐색 Sequential Search

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

정렬되지 않은 리스트에서 데이터 찾을 때 사용

 

이진 탐색 Binary Search

배열 내부의 데이터가 정렬되어있어야만 사용 가능함

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것

입력 데이터가 많거나 탐색 범위가 넒음

확인하는 원소의 개수가 절반씩 줄어들기 때문에 시간 복잡도 O(logN)

# 반복문
def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start+end)//2
        
        if array[mid] == target:
        	return mid
        elif array[mid]> target:
        	end = mid-1
        else:
        	start= mid+1
        return None

# 재귀함수 활용
def binary_search(array, target, start, end):
	if start > end:
    	return None
    mid = (start+end)//2
    
    if array[mid]==target:
    	return mid
    
    elif array[mid]>target:
    	return binary_search(array, target, start, mid-1)
    else:
    	return binary_search(array, target, mid+1, end)

 

트리 자료 구조

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 tree 자료구조를 이용해서 데이터가 정렬됨

노드와 노드의 연결로 표현

* 노드 : 정보의 단위, 어떠한 정보를 가지고 있는 개체

 

* 트리는 부모 노드와 자식 노드의 관계로 표현

* 트리의 최상단 노드가 루트 노드

* 트리의 최하단 노드는 단말 노드

* 트리의 일부를 떼어내도 트리 구조 -> 서브 트리

* 파일 시스템 같은 계층적이고 정렬된 데이터 다루기 적합

 

이진 탐색 트리

* 부모 노드보다 왼쪽 자식 노드가 작다

* 부모 노드보다 오른쪽 자식 노드가 크다

 

데이터 개수가 천만개를 넘거나 탐색 범위 크기가 천억 이상이면 이진 탐색 알고리즘 의심

# 입력 데이터가 많을 때
import sys

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