이진 검색
- 이진 검색
정렬된 배열에서 타겟을 찾는 검색 알고리즘
시간 복잡도가 O(log n)
정렬된 배열에서 값을 찾아내는 ‘알고리즘’
일반적인 탐색과 비교하면 배열이 작으면 성능이 떨어질 수 있지만 배열의 크기가 커질 수록 효과를 발휘함
- 이진 탐색 트리
정렬된 구조를 저장하고 탐색하는 ‘자료구조’
- 알고리즘
두 개의 포인터를 이용함
포인터 사이에서 중간 값을 찾은 후 원하는 값이 중간 값 보다 클/작을 시 왼쪽 포인터를 중값 값으로/오른쪽 포인터를 중간 값으로 옮기는 작업을 하며 값을 찾아냄
재귀, 반복으로 가능
- 이진 검색 모듈
bisect 모듈이 이진 검색 알고리즘 제공함
- 버그
가운데를 계산하는 left + right // 2 에서 left + right 가 자료형의 최댓값 초과하여 오버플로우가 발생할 수 있음
left + (right - left) // 2 로 방지
Python 에서는 임의 정밀도 정수형을 지원하기 때문에 해당되지 않음
- 재귀 제한
파이썬에는 재귀 호출에 대한 호춧 횟수 제한이 있으며 기본값 1,000으로 설정
값 바꿀 수 있지만 코딩 테스트 플랫폼에서는 설정 변경 허용하지 않음
- 슬라이싱 성능
슬라이싱은 매우 효율적이고 빠름
하지만 매번 새롭게 객체를 생성해서 할당하게 되고 매우 큰 배열의 경우 슬라이싱을 이용해 새로운 객체를 생성하는 데 많은 시간이 듦
- any(), all()
- any()
포함된 값 중 어느 하나가 참이라면 항상 True 출력
- all()
포함된 모든 값이 참이어야 True 출력