이진 탐색 알고리즘

 

 

이진 탐색 알고리즘을 수행하기 전 

 

한 가지 조건은 "배열에 저장된 데이터는 정렬이 되어있어야 한다." 이다. 

 

이진 탐색 알고리즘은 배열을 반으로 줄여나가면서 내가 찾고자 하는 값의 위치를 알아내기 때문이다. 

 

---

 

단계별로 소개해보면, 

 

1. 배열 인덱스의 시작과 끝을 더한다. 

2. 1의 결과값을 2로 나눈다. 

3. 2의 결과값이 인덱스가 되며, 저장된 값이 내가 원하는 값인지 확인한다. 

4-1. 맞음 

4-2. 아니라면 3에서의 저장된 인덱스 값과 내가 원하는 값의 대소를 비교한다. 

5. 인덱스를 기준으로 4의 결과에 의해 탐색의 범위를 제한할 수 있다. 

6. 다시 1으로 돌아가 제한된 인덱스의 시작과 끝을 더한다. 

7. 결과값을 2로 나눈다. (정수부분만 취함 

8. 인덱스에 저장된 값이 내가 원하는 값인지 확인한다. 

 

이렇게 내가 찾는 값을 얻을 때까지 계속해서 탐색해 나가면 된다. 

 

 

예시 

 

오름 차순 정렬된 배열이 존재한다. 

{3, 14, 23, 37, 45, 59, 68, 82, 100} 

 

내가 찾는 값은 23이라고 가정하자. 

 

인덱스 처음과 마지막 0과 8을 더한다. 

 

더한 값을 2로 나눈다. ==> 결과값 4 

 

4를 인덱스로 하여 값 45가 찾는 값 23인지 비교한다. 45 > 23 

 

이때 인덱스 값이 더 크기에 주어진 배열에서 탐색의 범위를 제한한다. 

{3, 14, 23, 37} 

 

다시 탐색 과정을 진행하여 인덱스 1을 얻었고, 인덱스 값이 14 임을 확인한다. 

 

대소비교 (14<23) 를 통해 인덱스 범위를 2~3으로 제한하고 인덱스를 더해서 2로 나눈다. 

 

주어진 결과 인덱스(2)의 값을 확인한다. 

 

23 == 23 

 

원하는 값을 찾았고, 탐색은 종료된다. 

 

총 3번의 탐색을 거쳐 원하는 값을 찾게 되었다. 

 

---

코드로 보면 다음과 같다. 

 

 

 

시간 복잡도는 

배열의 데이터 수 n이 1이 되기까지의 비교연산 횟수를 세어보고,

마지막으로 데이터 갯수가 1개만 남았을 때의 비교연산으로 구할 수 있다. 

 

따라서 위의 예제는 시간 복잡도가 3임을 확인할 수 있다. 

 

 

빅오 표기법을 이용하여 

시간 복잡도를 

T(n) = n**2 으로 간략화할 수 있다. 

 

 

빅오 표기법  (big-o Notation) 은 쉽게 말해

" 시간 복잡도 함수 T(n) 이 다항식으로 표기되었다면, 최고차항의 차수가 빅오가 된다. " 는 것이다.