[알고리즘 알아보기] 이분 탐색

https://basaeng.tistory.com/162

[1일 1알고] 징검다리 건너기

 

오늘 문제를 풀어보니 꼭 이분 탐색(이진탐색)은 헷갈리는 경우가 많더라고요

아무래도 제대로 알아본적이 없어서 그런 느낌입니다. 

 

이번 기회에 간단하게라도 알아보겠습니다.

---

이분 탐색

이분 탐색은 말그대로 전체를 두 부분으로 나눠가며 탐색하는 알고리즘입니다.

 

"0부터 100가지의 숫자 중 내가 생각하는 숫자를 맞춰봐!" 라고 했을 때 

가장 수학적으로 빠르게 찾는 방법은 50을 부르고 up/down에 따라 up이라면 75 down이라면 25를 부르는 식으로 점점 범위를 좁혀가는 것이 가장 효과적입니다.

 

반으로 나눈다는 것은 n에 대해 log2(n)을 취한다는 것이고 따라서 n이 클수록 더 큰 효과를 볼 수 있습니다.

---

이분 탐색 시 사용하는 변수

기본적으로 반을 자른 공간에서 왼쪽을 봐야할지, 오른쪽을 봐야할지를 판단하기 위해서는 

중간을 잡고 그 값으로 판단해야합니다.

 

그리고 중간을 잡기 위해서는 좌우 양끝이 필요합니다.

이를 위해 이분탐색에서는 3가지의 변수를 기본적으로 사용합니다.

(left, mid, right)

 

초기에는 left가 배열의 시작 혹은 가질 수 있는 최솟값, right는 배열의 끝 혹은 가질 수 있는 최댓값이 됩니다.

(물론 정렬된 배열 기준)

 

그렇다면 mid는 (left + mid) / 2 가 될 것입니다.

---

탐색 진행

만약에 찾는 값이 mid보다 작다면? left는 그대로 두고, right를 mid - 1로 하고 이후 탐색을 진행합니다.

만약에 찾는 값이 mid보다 크다면? right는 그대로 두고, left를 mid + 1로 하고 이후 탐색을 진행합니다.

---

종료 조건

이분탐색에서 가장 중요한 것이 종료조건이라고 생각합니다.

while문 안의 종결 조건을 잘 설정하지 않으면 꼭 조금씩 어긋나서 문제를 틀리게 되더라고요

 

물론 문제마다 다르지만 현재 설계의 경우 일반적으로 종료조건은 while(left <= right)입니다.

 

이 조건이 깨지는 경우는 left = right인 상황에서, left = mid + 1, right = mid - 1이 되는 순간입니다.

 

조건이 맞는 경우에 갱신하기 때문에 적절한 값이 answer가 될 것입니다.

---

일단은 간단하게 알아보았고

추가적으로 이분탐색 관련 문제를 풀면 이 아래에 추가해나가겠습니다.