1. 반복적 방법
1.1. 동작
1.2. 특징
1.
key값을 찾을 때까지 반복문은 탐색 범위를 반으로 줄이는 작업을 반복한다
2.
정렬된 상태에서 수행 가능
3.
key값을 갖는 원소가 여러 개 있을 때 원소들 중 어떤 원소의 인덱스를 반환할지 예측하기 힘들다
→ key값의 원소들 중 가장 작은 인덱스를 찾고 싶다면, 이진 탐색 후 반환된 인덱스에서 작은 인덱스 방향으로 다른 값이 나올 때까지 탐색하면 된다
1.3. 성능
•
최상의 경우 시간 복잡도
◦
key값을 가진 원소가 배열의 가운데에 있을 때
◦
가운데 원소와 key 값을 한 번의 비교 후 탐색 완료 →
•
최악의 경우 시간 복잡도
◦
탐색 범위를 더 이상 반으로 나눌 수 없을 때까지 줄여야 찾을 수 있는 인덱스에 key가 존재하는 경우
◦
배열의 원소 개수 을 2로 나눌 수 있는 횟수가 증가하면 수행 시간이 증가한다 →
•
공간 복잡도
◦
원소 개수가 늘어나도 알고리즘 수행에 필요한 메모리 크기는 같다 →
2. 재귀적 방법
2.1. 동작
2.2. 특징
1.
재귀 호출할 때마다 탐색 범위를 반으로 줄인다
2.
탐색이 끝나면 반환 시작
3.
1.2. 특징 의 2, 3번과 동일한 특징을 갖는다
2.3. 성능
•
시간 복잡도
◦
1.3. 성능 의 시간 복잡도와 같다
•
최상의 경우 공간 복잡도
◦
key값을 가진 원소가 배열의 가운데에 있을 때
◦
탐색 범위 크기에 상관없이 재귀 호출은 일어나지 않는다 →
•
촤악의 경우 공간 복잡도
◦
탐색 범위를 반으로 나눌 수 없을 때까지 줄여야 찾을 수 있는 인덱스에 key가 존재하는 경우
◦
leftIdx와 rightIdx의 차를 2로 나눌 수 있는 횟수가 증가할 때 재귀 호출 횟수가 증가
◦
leftIdx를 , rightIdx를 이라고 할 때 공간 복잡도는