[알고리즘] 이진탐색

이진탐색

이진탐색(Binary Search)은 반으로 쪼개가면 탐색하는 알고리즘이다.

단, 데이터가 정렬되어있다는 것을 전제조건으로 깔고 간다. 

 

이를 위해 시작, 끝, 중간점을 변수로 지정하여 찾으려는 값과 배열의 중간점에 있는 데이터를 반복적으로 비교한다!

 

시간복잡도 : O(logN)

 

코드 구현

#이진탐색은 전제조건을 정렬이다.
#처리해야할 데이터 개수나 값이 1000만 단위 이상으로 넘어가면 이진탐색과 같이 o(logn)의 속도를 내는 이진탐색을 고려야한다

def binary_search(array, target, start, end) :
    if start>end :
        return None
    pivot=(start+end)//2
    if array[pivot]==target :
        return pivot
    elif array[pivot]>target :
        return binary_search(array, target, start, pivot-1)
    elif array[pivot]<target :
        return binary_search(array, target, pivot+1, end)

n, target=list(map(int, input().split()))
array=list(map(int, input().split()))

result=binary_search(array, target, 0, n-1)
if result == None :
    print("존재하지 않음")
else :
    pirnt(result+1)



 

bisect 라이브러리

 

파이썬에서 이진탐색을 쉽게 이용할 수 있도록 라이브러리를 제공한다.

• bisect_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
• bisect_rigth(a,x) : 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

예를 들어 정렬된 리스트 [2, 3, 3, 6, 7, 8]이 들어있을 경우 3을 넣고자 한다고 치면 bisect_left(array, 3) 은 인덱스 1, bisect_rigth(array, 3)은 인덱스 3을 반환한다.

 

이 라이브러리를 이용해 특정 범위에 속하는 원소의 개수를 구할 때 용이하다. O(logN)으로 빠르게 계산가능!

트리 자료구조

트리 자료 구조란 노드와 노드의 연결로 표현

그래프 자료구조의 일종으로 데이터베이스 시스템에서 많은 양의 데이터를 관리하기 위해 사용된다고한다.

 

주요특징

• 부모노드와 자식노드의 관계료 표현
• 최상단 노드를 루트노드라고함
• 최하단 노드를 단말 노드라고 함
• 트리의 일부를 서브 트리라고 함
• 계층적이고 정렬된 데이터를 다루기에 적합

 

이진 탐색 트리

이진탐색이 동작될 수 있도록 구현된 자료구조이다.

모든 트리가 이진탐색트리는 아니다.

 

주요특징

• 부모 노드보다 왼쪽 자식 노드가 작음
• 부모 노드보다 오른쪽 자식 노드가 큼

 

※빠르게 입력받는 법!

 

주로 이진 탐색 문제는 입력 데이터가 많거나 탐색 범위가 넓은 편이므로 빠르게 입력받을 수 있는 sys 라이브러리를 사용하면 좋다!

 

사용방법

import sys

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

pirnt(input_data)

 

※해당 포스팅은 <이것이 취업을 위한 코딩테스트다 (나동빈 저)> 책을 참고하여 작성되었습니다.