이분탐색 내가 진짜 한방에 알려줄게
이분 탐색 들어는 봤니?
- 이진 탐색, 이진 검색 등등 여러 이름이 있는 Binary Search! 이름에서도 알 수 있듯이 이 알고리즘은 이진 == 2와 관련있습니다. 간단한 예를 들어보도록 하겠습니다.
- 자,
[1, 5, 3, 10, 2] 라는 배열이 있다고 하고, 우리는 여기서 5가 있는지, 5가 있다면 몇 번째 index에 있는지 알고 싶습니다. 딱 떠오르는 방법은 아마 아래와 같을 겁니다.
- 완전 탐색! 5가 있는지 없는지 처음부터 시작해서 확인해보겠다!
- 만약에 배열의 길이가 N이고, M번 도는 반복문 안에서 계속 확인을 해준다면,
O(MN)이라는 시간복잡도가 되겠습니다. 만약 N, M이 10만 이상이라면,,, 컴퓨터는 힘들다고 파업을 할것입니다.
- 그러면! 매핑을 사용해서 처음 한 번만 돌면 되는 것이 아니냐! 하시는 사람들도 있을겁니다. 그러나 만약 N이 10억이라면,,, 이것도 위와 같은 상황이 되겠죠?
- “그래서 어떡하라고?” 라는 궁금증을 해결하기 위해, 우리는 이분탐색을 배워볼 것입니다. 단순히 완전 탐색을 하는 것이 아니라, 다음과 같은 느낌으로 진행할 것입니다.
- 응? 찾으려는 것이 지금 보고 있는 값보다 작아? 그럼 애보다 큰 값들은 볼 필요가 없겠네?
- 응? 찾으려는 것이 지금 보고 있는 값보다 커? 그럼 애보다 작은 값들은 볼 필요가 없겠네?
- 그렇게 한다면, 전체를 확인할 필요 없이 전체의 절반의 절반의 절반의 절반의 ,,, 를 확인한다면
O(logN) 의 시간으로 단축을 시킬 수 있을 것입니다. 바로 본론으로 고고하도록 합시다!
이분 탐색을 위한 전처리!
- 위에서 언급했던 것처럼 우리는 어떠한 값을 기준으로 작은지/큰지 파악을 해서 해당하지 않는 부분들을 싸그리 잘라버려야 합니다. 그렇다면 어떠한 값을 기준으로 왼쪽에는 작은 값들이, 오른쪽에는 큰 값들이 존재해야 합니다. 이것을 위해 우리는 이분 탐색 하려는 배열을 정렬 해주어야 합니다.
[1, 5, 3, 10, 2] 을 [1, 2, 3, 5, 10] 으로 정렬해줘야, 3 보다 왼쪽에 있는 값들은 작고, 오른쪽에 있는 값은 크다는 것을 확신할 수 있습니다.
- 자, 이제 우리는 이분 탐색을 어떻게 하는지만 알면 됩니다.
어떻게 할까?
[1, 2, 3, 5, 10] 에서 2를 찾는다고 해봅시다. 그러면 우리는 다음과 같은 단계를 거칠 것입니다.
- 배열 전체에서 찾는 것이므로
left = 0, right = 4 를 시작으로 중간 값을 확인해줍니다. 여기서 0은 배열의 처음 인덱스, 4는 배열의 끝 인덱스 입니다.
left와 right의 중간 인덱스는 (left+right)//2 = 2 가 될 것입니다.- 중간 인덱스
2가 가르키는 값은 3입니다. 값 3은 찾으려는 값 2보다 크기 때문에, 우리는 값 3의 인덱스를 포함하여 오른쪽에 있는 값들은 봐줄 필요가 없습니다. (왜냐하면 그 오른쪽 값들은 무조건 값 3보다 크거나 같을 것이기 때문입니다.)
- 그러면 우리는
right를 중간 인덱스 2 보다 1 작은 인덱스 1로 만들어줍니다.
- 결과적으로
left = 0, right = 1 이 되고, 2번의 과정부터 다시 반복해주면 됩니다.
- 위의 과정은 정확히 일치하는 값을 찾는 것이고, 이분탐색의 종류는 총 3가지가 있습니다.
- 정확히 같은 값을 찾는 방법
- lower bound 값을 찾는 방법
- upper bound 값을 찾는 방법
- lower, upper bound 찾는 것은 찾으려는 배열안에 중복되는 값이 존재할 때 많이 씁니다. 방법은 위에서 설명한 틀에서 크게 벗어나지 않고,
left가 움직이느냐/right이 움직이느냐를 다르게 설정만 해주면 됩니다.
- 간단한 설명 그림을 보고, 코드로 바로 넘어가도록 합시다.
What about C++?
What about Python?
