이진검색(Binary Search)

이진검색(Binary Search)에 대해 알아보자. 이진검색 또한 검색 기법중 하나이다. 단 전제조건이 하나가 존재한다.

 

이진검색을 사용하기 위해서는 해당 배열의 데이터가 정렬(sort)되어있어야 한다.

 

* 결론적으로 이진검색인 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있도록 도와주는 알고리즘이라는 것이다.

 

예시를 하나 들어 [5,7,15,28,29,31,39,58,68,70,95] 라는 리스트가 있고, 나는 여기서 39라는 값을 검색하고 싶다고 가정하자. 가정하자. 우선 검색 범위의 시작 인덱스를 pl, 끝 인덱스를 pr, 중간 인덱스를 pc라고 부르기로 약속하자. 

 

과정에 대한 사진은 다음과 같다.

 

<이진검색 예제 풀이과정>

 

1) 우선 초기 검색범위는 당연히 처음(index 0)부터 끝(index 10)이다. 그리고 검색범위의 중간 인덱스는 5(0 + 10 // 2)이다. 인덱스 5에 대한 값인 31은 검색하고자 하는 값은 39보다 더 작은 값이다.  pl : 0, pr : 10, pc : 5

 

2) 검색하려는 값이 중간 인덱스의 값보다 더 크기 때문에, 시작 인덱스 값을 중간 인덱스보다 하나 큰 인덱스 6을 시작인덱스로 다시 정한다. 그렇게 되면 6 ~ 10 인덱스가 검색범위이며, 중간 인덱스는 8(6 + 10 // 2) 가 된다.  인덱스 8에 대한 값인 68은 검색하고자 하는 값인 39보다 더 큰 값이다. pl : 6 pr : 10 pc : 8

 

3) 검색하려는 값이 중간 인덱스의 값보다 작기 때문에 끝 인덱스 값을 중간 인덱스보다 하나 작은 7로 다시 정한다. 그렇게 되면 6~7인덱스가 검색범위이며, 중간인덱스는 6(6 + 7 // 2)이 된다. 인덱스 6의 값은 우리가 찾으려는 값은 39가 있는 인덱스이다. 그렇기 때문에 해당 인덱스인 6을 반환해준다.

 

 

* 결론적으로 두가지의 경우를 활용하는 것이다.

 

1) x[pc] < key 인 경우

 

x[pl] ~ x[pc]는 key보다 작은것이 되므로 검색 범위에서 제외하는 것이다. 그렇기에 검색범위를 a[pc + 1] ~ a[pr]로 좁혀준다. pl 이 pc + 1이 되는것이다.

 

2) x[pc] > key인 경우

 

x[pc] ~ x[pr]은 key보다 큰 것이 되므로 검색 범위에서 제외하는 것이다. 그렇기에 검색 범위를  a[pl] ~ a[pc - 1]로 좁혀준다. pr 이 pc - 1이 되는 것이다.

 

<이진검색의 시간복잡도>

평균 : logn

 

검색을 성공하는 경우 : logn - 1

 

검색을 실패하는 경우 : |log(n+1)| ( 여기서 |x| 는 가우스 기호가 아닌 천장함수이다. 천장함수란 x보다 크거나 같은 수중 가장 작은수를 의미한다. )

 

 

<이진검색의 종료조건 두가지>

 

1) 중간 인덱스의 실제값이 key값과 일치하는 경우

2) 검색범위에 key값이 없는 경우

 

 

이진 검색 예제 코드는 다음과 같다.