[ Algorithm ] 이진탐색 알고리즘

이진탐색 (Binary Search)

정렬이 되어있는 리스트에서 탐색 범위를 반씩 좁혀가며 데이터를 탐색하는 것이다.

각 단계마다 탐색 범위를 2로 나누어 탐색하기 때문에 시간복잡도는 O(log N)이다.

때문에 이진탐색은 매우 넓은 탐색범위(억 단위 이상)에서 최적의 해를 찾아야 하는 경우나

데이터를 정려한 후 다수의 쿼리를 날려야 하는 경우에 많이 사용할 수 있다.

 

이진탐색 동작 방식

아래 리스트 표에서 값이 15인 위치를 찾고자 한다고 가정해보자.

0

5

6

7

8

9

15

16

19

20

1. 정렬이 이미 되어 있다는 것을 가정하고 이를 통해서 [start, mid, end] 3포인트를 지정한다.
   mid는 배열의 크기를 2로 나누었을때 소수점을 버린 값이다. (10 = 5, 9 = 4)
   {start: 0, mid: 8, end: 20}
   
   
2. 이진탐색의 방식은 결과적으로 mid가 탐색값이 되면 탐색을 멈추고 mid를 반환하는 방식이다.
   탐색값과 mid를 비교해서 탐색값이 더 크다면 start = mid를 해주어 탐색 범위를 좁히고
   변경된 start를 기준으로 mid = parseInt((start + end) / 2) 를 작성해서 mid위치를 재지정해준다.
   반대로 탐색값이 더 작다면 end = mid, mid = parseInt((start + end) / 2)를 작성하여
   end위치와 mid위치를 재지정해주면 된다.

 

마치며...

이진 탐색코드 같은 경우엔 코딩테스트에서도 분명 이점이 있지만 프로젝트를 진행할 때 특정 값을 정렬된 데이터들 내에서 탐색하는 방법을 사용할때 많이 이용하게 될 것 같다.