[ALGORITHMS]문제 12 이분탐색

문제 12

이분탐색

자료가 크기 순서대로 정렬된 리스트에서 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘을 만들어 보세요. 리스트에 찾는 값이 없으면 -1을 돌려줍니다

이번 문제는 숫자가 여러개 들어 있는 리스트에서 특정한 값이 있는 위치를 돌려주고 리스트에 그 값이 없으면 -1를 결과값으로 돌려주는 문제 7과 똑같습니다. 

다만 이번에는 리스틩 자료가 순서대로 정렬되어 있으므로 훨씬 더 빠르게 탐색할 수 있습니다.

1. 일상생활 속의 탐색 문제

사람들은 일상 생활 속에서 알게 모르게 굉장히 많은 탐색 문제를 풀면서 살아갑니다.

첫번째 예로 두꺼운 책을 한권 앞에 두고 특정한 쪽 수(618쪽) 를 찾는 과정을 떠올려 봅시다

1. 우선 택의 중간쯤을 펼쳐 쪽수를 보니 520쪽입니다

2. 찾고자 하는 쪽 수가 펼친 쪽 수보다 크므로 (618>520) 펼친 곳의 앞쪽은 더 이상 찾을 필요가 없습니다.

3. 현재 펼친 곳에서 뒤쪽으로 적당해 보이는 곳을 다시펼치니 710쪽입니다.

4. 찾고자 하는 쪽 수가 펼친 쪽 수보다 작으므로(618<710) 펼친 곳의 뒤쪽은 더 이상 찾을 필요가 없습니다.

5. 이번에는 다시 앞쪽으로 책을 펼쳤더니 613쪽이 나옵니다.

6. 찾으려는 쪽 수와 가까운 쪽까지 왔으니 이제 쪽을 한장 한장 뒤로 넘깁니다.

7. 원하는 618쪽이 나오면 탐색을 멈춥니다.

- 책의 쪽 번호가 이미 정렬 되어 있으므로 특정 쪽의 앞쪽을 찾아봐야 할지 뒤 쪽을 찾아봐야 할지 바로 알 수 있습니다.

2. 이분 탐색 알고리즘

리스트 : [1, 4, 9, 16, 25, 36, 49 ,64 ,81]

찾는 값 :36

1. 먼저 전체 리스트의 중간 위치를 찾습니다. 위치 번호 4가 리스트의 중간 위치이고, 중간 위치 값은 25입니다

2. 찾는 값 36과 중간 위치를 찾습니다. 위치 번호 4가 리스트의 중간 위치이고, 중간 위치 값은 25입니다.

3. 이제 [36,49,64,81] 리스트에서 중간 위치를 찾습니다. 이 경우 49와 64의 한 가운데가 중간 위치가 되는데, 두 자료 중에 앞에 있는 값인 49를 중간 위치 값으로 뽑습니다.

4. 찾는 값 36과 중간 위치 값 49를 비교합니다. 36< 49이므로 찾는 값 36은 처음에 비교한 값인 25보다는 오른쪽에 있고 49보다는 왼쪽에 있습니다.

5. 25보다 오른쪽에 있고 49보다 왼쪽에 있는 값은 한개 뿐이므로 위치 번호 5의 36이 중간 위치입니다.

6. 찾는 값 36이 중간 위치 값과 같으므로 위치 번호 5를 결괏값으로 돌려주고 종료합니다.

- 이분 탐색의 원리를 일반적으로 정리하면 다음과 같습니다.

1. 중간위치를 찾습니다.

2. 찾는 값과 중간 위치 값을 비교합니다.

3. 같다면 원하는 값을 찾는 것이므로 위치번호를 결괏값으로 돌려줍니다.

4. 찾는 값이 중간 위치 값보다 크다면 중간 위치의 오른쪽을 대상으로 다시 탐색합니다(1번 과정부터 반복)

5. 찾는 값이 중간 위치 값보다 작다면 중간 위치의 왼쪽을 대상으로 다시 탐색합니다

(1번 과정부터 반복)

자료의 중간부터 시작해 찾을 값이 더 크면 오른쪽으로, 작으면 왼쪽으로 점프하며 자료를 찾습니다. 점프할 때마다 점프 거리는 절반씩 줄어듭니다.

* 이분 탐색 알고리즘

3. 알고리즘 분석

이분 탐색은 값을 비교할 때마다 찾는 값이 있을 범위를 절반씩 좁히면서 탐색하는 효율적인 탐색 알고리즘입니다.

 예를들어 자료가 천개 있을 때 원하는 자료를 찾는다고 생각해 보겠습니다.

순차 탐색은 최악의 경우에 자료 천개와 모두 비교해야 하지만, 이분 탐색은 최악의 경우에도 자료 열개와 비교하면 탐색을 마칠 수 있습니다.

이분 탐색의 계산 복잡도는  O(logN)으로 순차 탐색의 계산 복잡도인 O(n)보다 훨씬 효율적입니다.

물론 이분 탐색을 가능하게 하려면 자료를 미리 정렬해 둬야 해서 번거로울 수 있습니다. 하지만 필요한 값을 여러 번 찾아야 한다면 시간이 조금 걸리더라도 자료를 한번 정렬한 다음에 이분 탐색을 계속 이용하는 방법이 훨씬 효율적입니다

* 연습문제

12-1

다음 과정을 참고하여 재귀호출을 사용한 이분 탐색 알고리즘을 만들어 보세요

1. 주어진 탐색 대상이 비어 있다면 탐색할 필요가 없습니다.

2. 찾는 값과 주어진 탐색 대상의 중간 위치 값을 비교합니다

3. 찾는 값과 중간 위치 값이 같다면 결괏값으로 중간 위치 값을 돌려줍니다.

4. 찾는 값이 중간 위치 값보다 크다면 중간 위치의 오른쪽을 대상으로 이분 탐색 함수를 재귀 호출 합니다.

5. 찾는 값이 중간 위치 값보다 작다면 중간 위치의 왼쪽을 대상으로 이분 탐색함수를 재귀 호출합니다.

읽어주셔서 감사합니다