[자료구조] 1.2 알고리즘의 성능분석 방법 (3)

알고리즘의 성능분석 방법 (3)

이진 탐색 알고리즘

인덱스가 0~ 8 인 배열에서 탐색 대상이 3인 경우 이진 탐색

1. 배열의 0(시작 인덱스)과 8(끝 인덱스)을 더한 후 2로 나눈 결과 = 4 4를 기준으로 정한다.

2. arr[4]의 저장된 값을 탐색 값(3)과 비교

3. arr[4] > 3 이므로 탐색 범위를 인덱스 0~ 3으로 제한

4. 다시 배열의 0과 3을 더한 후 2로 나눈 결과 = 1 1을 기준으로 한다

5. arr[1]의 저장된 값을 탐색 값(3)과 비교

6. arr[1] < 3 이므로 탐색 범위를 인덱스 2~ 3으로 제한

7. 다시 배열의 2과 3을 더한 후 2로 나눈 결과 = 2(나머지는 버림) 2를 기준으로 한다

8. arr[2]의 저장된 값을 탐색 값(3) 과 비교

이진 탐색 특징

• 순차 탐색 알고리즘 보다 성능이 좋다
• 배열이 정렬되어 있어야 실행 가능하다
• 배열 탐색의 범위를 first와 last로 정했을 때 first > last 가 되기 전까지 탐색 진행
• first와 last가 나란한 경우는 탐색 대상이 하나 남았다는 것을 의미한다

참고

• 윤성우의 열혈 자료구조
  
• 윤성우의 열혈 자료구조 강의