[이진 검색]

이진 검색이란 정렬된 배열에서 타겟을 찾는 검색 알고리즘이다.

이진 검색은 값을 찾아내는 시간 복잡도가 O(log n)이라는 점에서 대표적인 로그 시간 알고리즘 이며, 이진 탐색 트리와도 유사한 점이 많다. 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 자료구조 라면, 이진 검색은 정렬된 배열에서 값을 찾아내는 알고리즘 자체를 의미한다.

1)이진 검색-하, 이진 검색

정렬된 nums를 입력받아 이진 검색으로 target에 해당하는 인덱스를 찾아라.

https://leetcode.com/problems/binary-search/

[팁!!!]

-반복, 재귀, 이진 검색 모듈, index를 사용해서 풀 수 있다.

-index의 경우 O(n)으로 점점 더 숫자가 증가할수록 느려져서 좋은 풀이법은 아니다.

-자료형을 초과하지 않는 위치 계산 방법: left + (right - left) //2

[재귀 제한]

파이썬에는 재귀 호출에 대한 호출 횟수 제한이 있으며, 기본 값은 1,000으로 설정되어 있다.

sys.getrecursionlimit()
>>>1000

일반적으로 코딩 테스트에서는 이 값을 변경 허용하지 않는다.

2)회선 정렬된 배열 검색-중, 이진 검색

특정 피벗을 기준으로 회전하여 정렬된 배열에서 target 값의 인덱스를 출력하라.