이분탐색

이분 탐색(Binary search) : 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘(리스트의 크기 N->logN의 시간)

 

ex) 1 2 3 4 5 6 7 8 9 (target = 6)

 

1. 중간에 있는 값을 찾는다. 

    1 2 3 4 5 6 7 8 9

 

2. 구하고자 하는 숫자와 타겟을 비교한다.

    1 2 3 4 5 6 7 8 9  (5 < 6) 

 

3. 타겟이 더 크기 때문에 5의 오른쪽 구간에서 타겟을 찾으면 된다.

    1 2 3 4 5 6 7 8 9

 

4. 타겟을 찾을때까지 1~3번을 반복하면 된다(만약 타겟이 더 작으면 반대로 5의 왼쪽 구간에서 찾으면 된다).