이분탐색 내가 진짜 한방에 알려줄게

이분 탐색 들어는 봤니?

  • 이진 탐색, 이진 검색 등등 여러 이름이 있는 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를 찾는다고 해봅시다. 그러면 우리는 다음과 같은 단계를 거칠 것입니다.
    1. 배열 전체에서 찾는 것이므로 left = 0, right = 4 를 시작으로 중간 값을 확인해줍니다. 여기서 0은 배열의 처음 인덱스, 4는 배열의 끝 인덱스 입니다.
    2. left와 right의 중간 인덱스는 (left+right)//2 = 2 가 될 것입니다.
    3. 중간 인덱스 2가 가르키는 값은 3입니다. 값 3은 찾으려는 값 2보다 크기 때문에, 우리는 값 3의 인덱스를 포함하여 오른쪽에 있는 값들은 봐줄 필요가 없습니다. (왜냐하면 그 오른쪽 값들은 무조건 값 3보다 크거나 같을 것이기 때문입니다.)
    4. 그러면 우리는 right를 중간 인덱스 2 보다 1 작은 인덱스 1로 만들어줍니다.
    5. 결과적으로 left = 0, right = 1 이 되고, 2번의 과정부터 다시 반복해주면 됩니다.
  • 위의 과정은 정확히 일치하는 값을 찾는 것이고, 이분탐색의 종류는 총 3가지가 있습니다.
    • 정확히 같은 값을 찾는 방법
    • lower bound 값을 찾는 방법
    • upper bound 값을 찾는 방법
  • lower, upper bound 찾는 것은 찾으려는 배열안에 중복되는 값이 존재할 때 많이 씁니다. 방법은 위에서 설명한 틀에서 크게 벗어나지 않고, left가 움직이느냐/right이 움직이느냐를 다르게 설정만 해주면 됩니다.
  • 간단한 설명 그림을 보고, 코드로 바로 넘어가도록 합시다.

bsearch

What about C++?

#include <iostream>
#include <vector>
using namespace std;
int binarySearch(int targetVal, vector<int>& arr){
//같은 값 찾기
int left = 0, right = arr.size() - 1;
while (left <= right){
int mid = (left + right) / 2;
//찾으려는 값이랑 같을 떄
if (arr[mid] == targetVal){
return mid;
}
//찾으려는 값보다 클 때
else if (arr[mid] > targetVal){
right = mid - 1;
}
//찾으려는 값보다 작을 때
else{
left = mid + 1;
}
}
//찾지 못했을 때
return -1;
}
int binarySearch2(int targetVal, vector<int>& arr){
//lower bound 찾기]
int left = 0, right = arr.size() - 1;
while (left <= right){
int mid = (left + right) / 2;
//찾으려는 값보다 크거나 같을 때
if (arr[mid] >= targetVal){
right = mid - 1;
}
//찾으려는 값보다 작을 때
else{
left = mid + 1;
}
}
//없는 경우도 있으므로, 찾으려는 값과 같은지 확인해야 한다.
return left;
}
int binarySearch3(int targetVal, vector<int>& arr){
//upper bound 찾기
int left = 0, right = arr.size() - 1;
while (left <= right){
int mid = (left + right) / 2;
//찾으려는 값보다 작거나 같을 때
if (arr[mid] <= targetVal){
left = mid + 1;
}
//찾으려는 값보다 클 때
else{
right = mid - 1;
}
}
//없는 경우도 있으므로, 찾으려는 값과 같은지 확인해야 한다.
return right;
}
int main(){
vector<int> arr = {1, 2, 5, 9, 10, 13, 15};
vector<int> arr2 = {1, 2, 2, 2, 5, 5, 5, 7, 8, 10};
cout << binarySearch(5, arr) << endl;
cout << binarySearch(10, arr) << endl;
cout << binarySearch(15, arr) << endl;
cout << binarySearch(100, arr) << endl;
cout << binarySearch(0, arr) << endl;
cout << binarySearch2(2, arr2) << endl;
cout << binarySearch2(0, arr2) << endl;
cout << binarySearch3(5, arr2) << endl;
cout << binarySearch3(11, arr2) << endl;
}
view raw test.cpp hosted with ❤ by GitHub

What about Python?

def binary_search(target_val):
#같은 값 찾기
left, right = 0, len(num_list)-1
while left <= right:
mid = (left + right) // 2
#찾으려는 값이랑 같을 때
if num_list[mid] == target_val:
return mid
#찾으려는 값보다 클 때
elif num_list[mid] > target_val:
right = mid - 1
#찾으려는 값보다 작을 때
else:
left = mid + 1
#찾지 못했을 떄
return -1
def binary_search2(target_val):
#lower bound 찾기
left, right = 0, len(num_list2) - 1
while left <= right:
mid = (left + right) // 2
#찾으려는 값보다 크거나 같을 떄
if num_list2[mid] >= target_val:
right = mid - 1
#찾으려는 값보다 작을 떄
else:
left = mid + 1
return left
def binary_search3(target_val):
#upper bound 찾기
left, right = 0, len(num_list2) - 1
while left <= right:
mid = (left + right) // 2
#찾으려는 값보다 작거나 같을 때
if num_list2[mid] <= target_val:
left = mid + 1
#찾으려는 값보다 클 때
else:
right = mid - 1
return right
num_list = [1, 2, 5, 9, 10, 13, 15]
print(binary_search(5)) #idx = 2, 결과값 = 2
print(binary_search(10)) #idx = 4, 결과값 = 4
print(binary_search(15)) #idx = 6, 결과값 = 6
print(binary_search(100)) #idx = 없음, 결과값 -1
print(binary_search(0)) #idx = 없음, 결과값 -1
num_list2 = [1, 2, 2, 2, 5, 5, 5, 7, 8, 10]
print(binary_search2(2)) #2의 lower_bound idx = 1, 결과값 1
print(binary_search2(0)) #3의 lower_bound idx = 없음, 결과값 0 (불일치)
print(binary_search3(5)) #5의 upper_bound idx = 5, 결과값 5
print(binary_search3(11)) #5의 upper_bound idx = 없음, 결과값 num_list의 길이 - 1 (불일치)
view raw test.py hosted with ❤ by GitHub