[탐색] 이진 탐색 (binary search)

이진탐색?

 

이진 탐색

이진탐색은 정렬된 배열에서 사용하기 좋은 탐색 알고리즘으로써,

배열 내 모든 엘리먼트를 전부 찾아가는 선형 탐색과는 달리 배열을 절반씩 잘라 탐색하여

필요한 부분을 효과적으로 찾아낼 수 있는 알고리즘이다.

즉, 정렬된 배열이 아니면 사용할 수 없는 알고리즘이다.

 

---

 

이진탐색에는 인덱스를 표시할 변수가 3개 필요하다.

여기서는 편의상 start, point, end라고 부르겠다.

• start : 탐색 범위를 지정해주는 시작 지점이 되며, 루프를 돌때마다 동적으로 바뀐다.
• point : 탐색 범위의 가운데를 짚어주는 인덱스이며, 언제나 (start + end) / 2 의 값을 가진다.
• end : 탐색 범위를 지정해주는 끝 지점이 되며, 루프를 돌 때마다 동적으로 바뀐다.

이 때 point가 굉장히 중요한 역할을 하게 되는데,

• point가 짚은 위치의 엘리먼트가 내가 찾는 값보다 작다면
  point에 -1을 한 인덱스가 end 인덱스로 바뀌게 된다.
  (point는 이미 탐색한 것과 같으니, -1을 한 값을 할당해준다.)
• point가 짚은 위치의 엘리먼트가 내가 찾는 값보다 크다면
  point에 +1을 한 인덱스가 start 인덱스로 바뀌게 된다. 
  (point는 이미 탐색한 것과 같으니,  +1한 값을 할당해준다.)

 

즉,

이진 탐색은 아래와 같은 알고리즘으로 나타낼 수 있다.

/*
이진탐색 알고리즘

문제)) 정렬된 배열과 찾고자 하는 값을 인수로 받으며,
찾고자 하는 값이 배열 내에 있다면 그 위치의 인덱스를 리턴하고,
없다면 -1을 리턴하라.

*/

function binarySearch(arr, val){
    let start = 0                                 // (1)
    let end = arr.length - 1                      // (2)
    let point = Math.floor((start + end) / 2)     // (3)
    while (arr[point] !== val && start <= end ) { // (4)
        if (arr[point] < val) start = point + 1   // (5)
        if (arr[point] > val) end = point - 1     // (6)
        point = Math.floor((start + end) / 2)     // (7)
    }
    if (arr[point] === val) return point          // (8)
    return -1 // 값을 못찾았다면 -1을 리턴해줌
}

/*

 (1) 초기 start 지점을 만들어줌. 시작값은 0임.
 (2) 초기 end 지점을 만들어줌. 시작값은 배열의 끝(array.length - 1)임.
 (3) 초기 point 지점을 만들어줌. 시작값은 start와 end의 중간값임.
     JS에서 정수를 나누면 소숫점까지 반환하므로 Math.floor를 통해 반내림함.
 (4) 루프조건. arr[point]가 찾는 값이 아닐때, 그리고 탐색하는 start가 end보다 작을 때 루프함
   - arr[point]가 val과 같은 값이 나오면 이미 값을 찾은 것이므로 루프할 필요가 없음.
   - 만약, 찾고자 하는 값이 배열 내에 없다면 start와 end 포인터가 같은 위치에 있게 됨.
     그럴 경우, 루프를 탈출해야함.
 (5) 만약 point가 위치한 값이 val보다 작다면 start를 point + 1한 위치로 당겨줌.
 (6) 만약 point가 위치한 값이 val보다 크다면 end를 point - 1한 위치로 당겨줌.
   - (5)와 (6)을 통해 탐색하는 범위가 계속 반으로 줄어듦.
 (7) start와 end가 재설정되었으므로, point도 재설정해줌.
 (8) 탈출문을 나왔을 때, 내가 찾은 값이 맞다면? 정답 인덱스를 리턴해줌
 
*/

 

 

이진탐색 시간복잡도 : O(logN)

이진탐색의 시간복잡도는 O(logN)이다.

log 복잡도는 무엇이라 설명해야할까?

아래 그림으로 살펴보자.

일단은 알고리즘을 돌려보아야 O(logN)이 뭔지 설명할 수 있다.

 

아래는 0부터 15까지 총 16개의 엘리멘트가 정렬되어있는 배열에서

숫자 2를 찾는 것에 이진탐색 알고리즘을 도입한 것이다. (위의 알고리즘을 도입했다.)

 

왼쪽으로 치우쳐저 보이지만 7이 가운데 인덱스이다.

 

일단 이진탐색 알고리즘으로 탐색이 시작되면,

배열의 정가운데에 위치하는 인덱스가 첫번째 point로 찍히게 된다.

이 때, point가 찍은 엘리먼트는 우리가 찾는 2보다 작다.

그럼 탐색의 범위를 줄이기 위해 point -1 의 값이 end로 재할당 되고,

point도 (start + end) / 2 로 재할당된다.

 

첫번째 순회 이루어졌다.

 

그럼 기존의 포인터 - 1에 해당하는 인덱스가 다음 값의 end가 된다.

탐색 범위가 줄었지만

이번에도 point 인덱스 값보다 찾고자 하는 값(2)이 더 작다.

그럼 알고리즘의 로직에 따라, 아래 그림과 같이 start, end, point 지점이 바뀐다.

 

이는 두번째 순회이다.

 

포인터의 -1이 된 값이 end가 된다.

탐색 범위를 또 줄였다.

하지만 이번에는 point의 값이 내가 찾고자 하는 값보다 더 크다.

이때는 point를 +1한 값이 start 지점이 된다. 

 

세번째 순회이다.

 

포인터 +1한 값이 start가 된다.

이렇게 될 경우

start와 end가 겹치게 된다.

같은 값을 더해서 2를 나누면 어쨌든 똑같은 값이니

start와 end와 point 모두 같은 위치에 있게 된다.

 

이 경우 start와 end가 같은 위치에 있으니 while문이 깨지게 되고

아래 if문에 따라 값이 결정 될 것이다.

내가 찾고자 하는 값은 2이고

 

arr[point]는 2이므로

정답을 반환하게 된다.

여기까지 네번째 순회이다. 네번째 연산에서 답이 도출되었다.

 

---

여기서 16개의 엘리먼트를 도는데 총 4번의 순회가 이루어졌다.

4의 제곱은 16이다.

즉, log2 16은 4이다.

log2에서 밑수는 보통 생략해서 logN이라고 부른다.

따라서 이진 탐색의 시간복잡도는 O(logN) 이다.

탐색해야할 엘리먼트를 절반씩 잘라가며 순회를 하다보니 이러한 시간복잡도가 나오게 된다.