[컴][알고리즘] Binary Search 바이너리 검색

바이너리 서치 / 검색 알고리즘 / binary search




binary search 를 설명해 주는 그림

http://mrweiprogramming.wikispaces.com/home#wk10

binary search 설명해 주는 동영상

http://www.youtube.com/watch?v=wNVCJj642n4

개념

정렬이 되어 있는 리스트를 가지고 작업한다.

바이너리라는 말과 연관되듯이
이진 즉, 양쪽,
여기서는 왼쪽 오른쪽중 어느 쪽으로 갈 것인지를 정하는 것이다.

이건 우리가 마치 up, down하는 느낌이다.
이 up, down 을 결정하는 것이 binary search 다. 이 up down 을 아이템이 2개가 있을 때 한다면 원하는 것을 찾게 된다.
이런 방식으로 up down 을 통해 범위를 좁혀나가면서 결국 찾게 되는 것이다.
그러니까 바이너리 서치는 그냥 up down 의 결정이라고 보면 된다.

일단 가운데 값을 던진다. 그러면 그 값보다 크다 작다를 얘기 해 준다. 작으면 왼쪽부분을 가지고 다시 물어본다. 반대로 크면 오른쪽 부분을 가지고 묻는다.
그런 식으로 계속 물어나가면서 찾게 된다.

찾으면 끝. 그리고, 계속 찾다가 결국 못찾는 경우도 끝.

동작

전제 : 왼쪽은 작은 값이고, 오른쪽으로 갈 수록 큰 값으로 정렬이 되어 있다

1. left <= right 이면 "찾으려는 값(target)" 을 "가운데에 있는 값(middle)"과 비교한다.
2. target < middle (찾으려는 값이 가운데에 있는 값보다 앞에 있다.)
3. middle바로 앞에 있는 값을(middle-1) 가장 오른쪽에 있는 값(right) 으로 하고, 1번부터 다시 반복한다.
4. 2번이 아닌 경우, target > middle(찾으려는 값이 가운데에 있는 값보다 뒤에 있다.)
5. middle 바로 뒤에 있는 값(middle + 1) 을 가장 왼쪽에 있는 값(left) 으로 하고, 1번부터 다시 반복한다.
6. 2번, 4번이 아닌경우, target == middle(찾으려는 값과 가운데 있는 값이 같다.)
7. target 을 찾았다.

See Also

1. 이진탐색 알고리즘