이진 탐색 (Binary Search)

 

📌  이진 탐색이란?

이진 탐색(Binary Search)는 정렬되어 있는 데이터가 있을 때 탐색 범위를 절반씩 좁혀가며 탐색하는 알고리즘이다. 이진 탐색에서는 위치를 나타내는 변수 3개(시작점, 중간점, 끝점)을 사용해, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 이진 탐색은 데이터를 절반씩 줄어들도록 만들기 때문에 시간 복작도가 O(logN)이다. 

// 재귀 함수로 구현
int binarySearch(vector<int> &arr, int target, int start, int end) {
    if (start > end) return -1;
    int mid = (start + end) / 2;

    if (arr[mid] == target) return mid;
    else if (arr[mid] > target) return binarySearch(arr, target, start, mid-1);
    else return binarySearch(arr, target, mid+1, end);
}

// 반복문으로 구현
int binarySearch(vector<int> &arr, int target, int start, int end) {
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

 

코딩테스트에서 이진 탐색 문제는 탐색범위가 큰 상황에서의 탐색을 가정하는 문제가 많다. 따라서 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근해보는 것이 좋다. 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다. 또 이런 문제의 경우 입력받는 데이터의 양이 많이 시간초과가 날 수 있으니 유의하길 바란다.

 

c++에서는 아래 코드를 main() 안에 넣어주면 된다.

ios::sync_with_stdio(false);
cin.tie(NULL);

 

파이썬에서는 input() 대신 sys 라이브러리의 readline()를 이용하면 된다. 

import sys

input_data = sys.stdin.readline().rstrip()

 

 

 

🔗  참고 자료 

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서