binary search
파이썬으로 이진 탐색 구현하기
이진 탐색(binary search)은 정렬된 데이터에서 특정한 값을 아주 빠르게 찾는 방법이다. N개의 데이터 중에서 특정한 값 x를 찾을 때, 최악의 경우 N번의 비교가 필요한데, 이진 탐색의 경우 최대 만큼의 비교를 하게 된다. 즉 자료의 크기가 클수록 선형 탐색에 비해 성능이 매우 우수해진다. 다만 이진 탐색은 자료가 정렬되어 있다는
이진탐색
bisect
bisect - 이진탐색 알고리듬
이진탐색은 데이터가 정렬된 상태일 때, 특정한 값을 매우 우수한 성능으로 탐색할 수 있는 알고리듬으로 실제로도 널리 이용된다. 이진탐색은 정렬된 데이터에서 특정한 값을 찾을 때 사람이 하는 것과 유사하게 처리되는데, 리스트의 한 가운데 지점의 값을 비교하여 찾는 값이 그보다 작으면 왼쪽에 그보다 크면 오른쪽에 있다는 것으로 탐색 범위를 매 시행마다 절반으로
ADT
이진탐색트리 (Binary Search Tree) 구현하기 - python
Binary Search Tree 이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한