7장 이진 탐색

0. 순차 탐색

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
• 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다.
  하지만 시간은 충분하지 않은 경우가 많다.
• 시간 복잡도: O(N)

1. 이진 탐색: 반으로 쪼개면서 탐색하기

• 전제: 배열 내부의 데이터가 정렬되어 있다.
• 탐색 범위를 절반씩 좁혀가며 탐색
• 사용 변수: 시작점, 끝점, 중간점
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터 탐색
• 시간 복잡도: O(logN)

  (이진 탐색 실행과정 생략)

2. 구현 방법

1. 재귀함수

• 원하는 데이터와 중간 값을 비교
• 원하는 데이터가 중간 값보다 작으면 끝점을 중간 값-1로 함수 재귀 호출
• 원하는 데이터가 중간 값보다 크면 시작점을 중간 값+1로 함수 재귀호출
• 재귀 종료 조건은 시작점> 끝점

소스 코드

#include <iostream>
#include <vector>

using namespace std;

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 n, target;
vector<int> arr;

int main(void) {
    cin >> n >> target;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    int result = binarySearch(arr, target, 0, n - 1);

    if (result == -1) {
        cout << "원소가 존재하지 않습니다." << '\n';
    }
    else {
        cout << result + 1 << '\n';
    }
}

2. 반복문

• 재귀함수와 유사하다.
• 함수를 재귀 호출하는 대신 시작점 또는 끝점을 재설정하고 반복문을 반복한다.
• 반복문 종료 조건은 시작점>끝점(재귀 함수 종료 조건과 동일)

소스코드

#include <iostream>
#include <vector>

using namespace std;

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;
}

int n, target;
vector<int> arr;

int main(void) {
    cin >> n >> target;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    int result = binarySearch(arr, target, 0, n - 1);

    if (result == -1) {
        cout << "원소가 존재하지 않습니다." << '\n';
    }
    else {
        cout << result + 1 << '\n';
    }
}

3. 예제 문제

1. 부품 찾기

2. 떡볶이 떡 만들기